Komplexität des monotonen (+, 2) SAT-Problems?

7

Um diesen Beitrag fortzusetzen , definieren wir das monotone -SAT-Problem:(+,2−)

Gegeben eine monotone CNF-Formel , bei der jede Variable genau einmal erscheint (als positives Literal), und eine monotone 2-CNF-Formel definiert für dieselben Variablen wie , wobei alle Variablen negiert werden. Ist erfüllbar?F+F2−F+F+∧F2- -

Ist dieses Problem NP-vollständig?

complexity-theory np-complete decision-problem complexity-classes Xavier Labouze
quelle

Antworten:

5

Dies ist NP-vollständig. Tatsächlich bleibt es NP-vollständig, wenn auf 3-CNF-Form (nicht nur CNF) beschränkt ist.F.+

Der Beweis besteht darin, zu zeigen, dass dieses Problem mindestens so schwierig ist wie das Testen der 3-Färbbarkeit eines Diagramms. Die Korrespondenz ist sauber und elegant. Sei ein ungerichteter Graph. Führen Sie die Variablen für und , um eine Dreifarbigkeit des Diagramms darzustellen. Hier bedeutet , dass wir dem Scheitelpunkt die Farbe .G=(V.,E.)xv,cv∈V.c∈{1,2,3}}xv,cvc

Um darzustellen, dass jeder Scheitelpunkt mindestens eine Farbe erhalten muss, werden wir für jeden Scheitelpunkt Klauseln einführen . Dies gibt uns , dhxv,1∨xv,2∨xv,3vF.+

F.+≡⋀v∈V.(xv,1∨xv,2∨xv,3).

Um darzustellen, dass keine zwei Endpunkte einer einzelnen Kante dieselbe Farbe erhalten dürfen, führen wir für jede Kante eine Klausel . Und um darzustellen, dass kein Scheitelpunkt mehr als eine Farbe erhalten darf, werden wir für jedes eine Klausel einführen. so dass Es sei die entsprechende Formel.¬xu,c∨¬xv,c(u,v)∈E.¬xv,c∨¬xv,c'c,c'∈{1,2,3}}c≠c'.F.2- -

F.2- -≡⋀(u,v)∈E.(¬xu,c∨¬xv,c)∧⋀v∈V.,c≠c'(¬xv,c∨¬xv,c').

Dann ist leicht zu erkennen, dass genau dann erfüllbar ist, wenn eine 3-Färbung hat. Tatsächlich entspricht jede zufriedenstellende Zuordnung von sofort einer 3-Färbung von und umgekehrt. Daher ist das Testen der Erfüllbarkeit dieser Klasse von Formeln mindestens so schwierig wie das Testen der 3-Färbbarkeit eines ungerichteten Graphen, daher ist es NP-hart.F.+∧F.2- -GF.+∧F.2- -G

DW
quelle
Ihre Übereinstimmung mit der 3-Färbbarkeit ist in der Tat klar. Daher ist das monotone SAT-Problem eindeutig NP-vollständig. Trotzdem ist (für mich) immer noch nicht klar, dass eine monotone CNF-Formel einer monotonen 3-CNF-Formel entsprechen kann. (3+,2- -)
Xavier Labouze
schöne reduktion!
Vor dem
@ XavierLabouze, sorry, du hast mich verloren. Ich habe nicht behauptet, dass jede CNF-Monotone-Formel einer 3-CNF-Monotone-Formel entspricht, und das wird zu keinem Zeitpunkt meiner Reduktion benötigt. Ich benutze die Tatsache, dass jede 3-CNF-Formel auch eine CNF-Formel ist (dies ist trivial), woraus folgt, dass das Problem im ursprünglichen Beitrag auch NP-vollständig ist.
DW
@ DW Richtig. Ich meinte, die Reduzierung von SAT auf SAT ist nicht so klar wie die von SAT auf 3-SAT. (+,2- -)(3+,2- -)
Xavier Labouze
Ich habe nach einem kleinstmöglichen expliziten Beispiel für SAT gesucht, das von Hand unbefriedigend und überprüfbar ist. Ich wäre Ihnen sehr dankbar, wenn Sie mir bei einem helfen könnten. (3+,2−)
TheoryQuest1