Überprüfung der einzigartigen SAT-Lösungen

Stellen Sie sich das folgende Problem vor: Gibt es bei einer CNF-Formel und einer Zuweisung, die diese Formel erfüllt, eine andere zufriedenstellende Zuweisung für diese Formel?

Wie komplex ist dieses Problem? (Es ist sicherlich in NP, aber ist es auch NP-schwer?)

Was ist, wenn Sie die Aufgabe nicht erhalten und nur entscheiden möchten, ob die Formel eine eindeutige befriedigende Aufgabe hat?

Vielen Dank.

Das Problem, zu entscheiden, ob eine gegebene CNF-Formel eine andere zufriedenstellende Zuordnung als eine gegebene hat, wird leicht als NP-vollständig gezeigt, indem eine CNF-Formel transformiert wird, um eine triviale Lösung hinzuzufügen. Dieses Problem wird in [YS03] als „Another Solution Problem (ASP) of SAT“ bezeichnet. Hiermit wird systematisch bewiesen, dass (die Entscheidungsversionen von) den ASPs vieler anderer Probleme ebenfalls NP-vollständig sind.

Das Problem, zu entscheiden, ob eine gegebene CNF-Formel eine eindeutige befriedigende Zuweisung hat oder nicht (Sie müssen also mit "Nein" antworten, wenn die Formel keine befriedigenden Zuweisungen oder mehr als eine befriedigende Zuweisung hat), ist in den USA vollständig. US enthält sowohl UP als auch coNP .

Verweise

[YS03] Takayuki Yato und Takahiro Seta. Komplexität und Vollständigkeit der Suche nach einer anderen Lösung und deren Anwendung auf Rätsel. IEICE-Transaktionen zu Grundlagen der Elektronik, Kommunikation und Informatik, E86-A (5): 1052–1060, Mai 2003.

Bearbeiten : Eine frühere Version (Revision 1) dieser Antwort enthielt eine Verwechslung zwischen der Entscheidungsversion und der Suchversion. Es wurde behoben.

Ich erinnere mich, dass Yoram Moses und ich dieses Problem Mitte der 1980er Jahre (im Lichte einiger Anwendungen) studierten und entdeckten, dass für viele natürliche NPC-Probleme das Problem, eine zweite / alternative Lösung zu finden (oder zu entscheiden, ob es eine solche gibt), NPC ist. Wir fanden dann heraus, dass dies bekannt war, aber ich erinnere mich nicht an den Schiedsrichter und konnte keinen finden (dh einen vor Mitte der 1980er Jahre). Aber ich bin sicher, ich erinnere mich richtig an das oben Gesagte.

Nur ein Kommentar zu Ryan. Die Tatsache, dass ein Theorem in aktuellen Klassen als Übung gegeben werden kann, macht es nicht weniger attraktiv. Es sollte in einem Artikel veröffentlicht worden sein, der zum Zeitpunkt seiner Entdeckung einen angemessenen Titel trug ...

Oded Goldreich

Hier schreibe ich einen Auszug aus folgendem Artikel:

Valiant, LG und Vazirani, VV 1986. NP ist so einfach wie das Erkennen einzigartiger Lösungen. Theor. Comput. Sci. 47, 1 (November 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Für jedes bekannte NP-vollständige Problem variiert die Anzahl der Lösungen seiner Instanzen über einen großen Bereich von null bis zu exponentiell vielen. Es ist daher natürlich zu fragen, ob die inhärente Unlösbarkeit des NP-vollständigen Problems durch diese große Variation verursacht wird. Wir geben eine negative Antwort auf diese Frage unter Verwendung des Begriffs der randomisierten Polynomzeitreduzierbarkeit. Wir zeigen, dass die Probleme der Unterscheidung zwischen SAT-Instanzen mit Null- oder Eins-Lösung oder der Suche nach Lösungen für SAT-Instanzen mit einer eindeutigen Lösung bei zufälligen Reduktionen so schwer wie SAT sind.

Ich schlage auch vor, das entsprechende Papier zu lesen:

Beigel, R., Buhrman, H. und Fortnow, L. 1998. NP ist möglicherweise nicht so einfach wie das Auffinden einzigartiger Lösungen. In Proceedings des dreißigsten jährlichen ACM-Symposiums für Computertheorie (Dallas, Texas, Vereinigte Staaten, 24. - 26. Mai 1998). STOC '98. ACM, New York, NY, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

$DP=\{(L_1 ∩ L_2)| L_1 \in NP, L_2\in CoNP\}$

Andreas Blass und Yuri Gurevich über das einzigartige Erfüllbarkeitsproblem

Die Lösung für beide Probleme, EINZIGARTIGES SAT sowie EIN ANDERES SAT, mit einer vollständigen Klassifizierung der Komplexität, ist in der Veröffentlichung zu finden

L. Juban: Dichotomiesatz für das verallgemeinerte eindeutige Erfüllbarkeitsproblem http://link.springer.com/chapter/10.1007%2F3-540-48321-7_27