Eine Variante von Critical SAT in DP

Eine Sprache gehört zur Klasse wenn es zwei Sprachen und so dass$L$$DP$$L1 \in NP$$L2 \in coNP$$L = L1 \cap L2$

Ein kanonisches vollständiges Problem ist SAT-UNSAT: Ist es bei zwei 3-CNF-Ausdrücken, und , wahr, dass erfüllbar ist und nicht?$DP$$F$$G$$F$$G$

Es ist auch bekannt, dass das kritische SAT-Problem vollständig ist: Ist es bei einem 3-CNF-Ausdruck wahr, dass erfüllbar ist, aber das Löschen einer Klausel macht es erfüllbar?$DP$$F$$F$

Ich betrachte die folgende Variante des kritischen SAT-Problems: Ist es bei einem 3-CNF-Ausdruck wahr, dass erfüllt werden kann, aber das Hinzufügen einer 3-Klausel (von aber unter Verwendung der gleichen Variablen wie ) macht es unbefriedigend? Aber es gelingt mir nicht, eine Reduzierung von SAT-UNSAT zu finden oder sogar zu beweisen, dass es oder schwer ist.$F$$F$$F$$F$$NP$$coNP$

Meine Frage: Ist diese Variante DP-komplett?

Danke für deine Antworten.

[Ich habe es zu einer richtigen Antwort gemacht, b / c jemand hat es -1 gegeben]

Wenn eine Klausel hinzugefügt werden darf, ist die Sprache leer - zu jeder erfüllbaren Formel können Sie eine 3-Klausel hinzufügen , die aus Variablen besteht, die nicht in : sind befriedigend sein.$F$$c$$F$$F \cup \{ c \}$

Wenn die hinzugefügten Klauseln Variablen von , ist die Sprache in P.$F$

Die Begründung lautet wie folgt:

Nehmen Sie ein beliebiges , dh und für eine beliebige 3-Klausel für Variablen von , . Sagen Sie , wobei ein Literal ist. Da UNSAT ist, alle Modelle von muss (für ) - denn wenn einige Modelle haben zB , dann würde es genügen und so . Nehmen wir nun an, dass es eine andere Klausel gibt, die genau wie$F \in L$$F \in SAT$$c$$F$$F \cup \{c\} \in UNSAT$$c = l_1 \lor l_2 \lor l_3 \notin F$$l_i$$F \cup \{ c \}$$F$$l_i=0$$i=1,2,3$$l_1=1$$c$$F \cup \{c\}$$c'$$c$, aber mit einem oder mehreren umgedrehten Literalen und so, dass , sagen Sie . Dann mit dem gleichen Argument alle Modelle von muss . Die notwendige Bedingung für ist also, dass es für jede Klausel genau 6 andere Klauseln in , die die drei Variablen von - nennen wir diese 7-Klausel-Teilmengen von Blöcken . Beachten Sie, dass jeder Block eine eindeutige zufriedenstellende Zuordnung zu seinen Variablen impliziert. Wenn diese notwendige Bedingung erfüllt ist, wird$c' \notin F$$c' = \neg l_1 \lor l_2 \lor l_3$$F$$l_1 = 1$$F \in L$$c \in F$$F$$c$$F$ $F$ist entweder eindeutig erfüllbar oder unbefriedigend. Die beiden Fälle können unterschieden werden, indem geprüft wird, ob die durch die Blöcke von implizierten Zuordnungen aufeinander treffen, was eindeutig in linearer Zeit erfolgen kann.$F$

Darf ich dank Ihrer Kommentare eine Antwort auf meine eigene Frage vorschlagen: Die Variante von Critical SAT ist in P.

Nennen wir "Problem 1" die Variante von Critical SAT: Ist es bei einem 3-CNF-Ausdruck wahr, dass F erfüllbar ist, aber das Hinzufügen einer Klausel aus F macht es unbefriedigend?$F$$F$$F$

Und "Problem 2": Stimmt es bei einem 3-CNF-Ausdruck , dass F alle darin enthaltenen Klauseln enthält und ein eindeutiges Modell hat?$F$$F$

Bei einer 3-CNF Formel .$F$

$F$$F$$F$$F$$F$$F$

$F$$F$$F$$F$$F$$F$$F$$F$$F$

$F$$F$

$F$$\binom{n}{3}$$\frac{n(n-1)(n-2)}{3}$$n$