2-Bevredigingsprobleem-Of 'n unieke waarheidsopdrag bestaan ​​of nie

Question

Ek het 'n probleem wat 'n uitbreiding van 2-SAT-probleem is.In standaard 2-SAT-probleem kan ons enige van die waarheidsopdragte vind wat afhang van die volgorde van hoekpunte wat ons kies.Ek wil kyk of daar een en slegs een waarheidsopdrag bestaan ​​(d.w.s. slegs een kombinasie) waarvoor die uitdrukking bevredigend is.Die aantal letterlikes kan 100 000 wees.Een manier is om al die moontlike waarheidsopdragte te vind en dit dan te vergelyk as hulle onderskeibaar is.Maar die probleem is vir elke vergelyking, ek sal 100000 waardes (geen letterlike) moet vergelyk.Is daar enige doeltreffende manier?

Answer 1

Feder (1994) beskryf 'n algoritme vir alle oplossings doeltreffend lys op 'n gegewe 2- satisfiability byvoorbeeld . Daar is ook aanhalings in die artikel vir algoritmes om die aantal opdragte tel, maar jy moet net om te probeer notering twee opdragte, wat meer doeltreffend kan wees.