Komplexität von 3SAT -Varianten

Question

Diese Frage ist von meinem motiviert Antworten zu einer anderen Frage, in der ich die Tatsache feststellte, dass sowohl Probleme zwischen Betweeness und Nicht-Betweeness $ np $ -Complete sind. Im ersteren Problem gibt es eine Gesamtreihenfolge, dass die Betweeness -Einschränkung jedes Triple durchgesetzt wird, während im späteren Problem eine Gesamtreihenfolge so ist, dass die Betweeness -Einschränkung jedes Triple verletzt wird.

Was ist die Komplexität der folgenden 3SAT -Varianten ?:

3sat_1 = {($ phi $): $ phi $ hat eine Aufgabe, die jede Klausel falsch macht}

3sat_2 = {($ phi $): $ phi $ hat eine Aufgabe, so dass genau die Hälfte der Klauseln wahr ist und die andere Hälfte falsch} ist}

Answer 1

3sat_1 ist einfach und eine Variante von 3SAT_2 ist NP-Vervollständigung. Ich vermute, dass 3sat_2 auch NP-Complete ist. UPDATE: Meine Vermutung ist unten nachgewiesen.

Sei $ c = x lor y lor z $ eine Klausel. Dann $ lnot c = lnot x land lnot y land lnot z $. Eine Aufgabe macht jede Klausel von $ phi $ false, wenn sie alle Negationen wahr macht. Die Konjunktion der Negation aller Klauseln ist nur eine große Konjunktion. Eine Konjunktion ist befriedigend, wenn sie nur dann eine Variable und ihre Negation enthält. Also ist 3sat_1 in p (in der Tat ist es in ac $^0 $).

In der Variante von 3SAT_2 wird gefragt, ob $ phi $ eine Aufgabe hat, die genau $ 8/9 $ $ der Klauseln stimmt. Dies ist eindeutig in NP. Um 3SAT auf diese Variante zu reduzieren, nehmen Sie die Formel $ phi $ und für jede Klausel $ C $ $ phi $ fügen Sie die acht Klauseln $$ hinzu (x_c lor y_c lor z_c) land cdots Land ( lnot x_c lor lnot y_c lor lnot z_c). $$ In jeder Zuordnung sind genau sieben davon korrekt. Insgesamt haben wir 9 $ | Phi | $ Clausses. Von den $ 8 | phi | $, die wir hinzugefügt haben, sind genau $ 7 | phi | $ immer korrekt. Daher ist $ phi $ befriedigend, wenn und nur wenn in der neuen Formel genau 8 $ 8 | Phi |

UPDATE: Hier ist eine Reduzierung von 3SAT zu 3SAT_2 selbst. Betrachten Sie bei einer Formel $ phi $ zwei Fälle. Der erste Fall ist, wenn wir alle Klauseln in $ phi $ gleichzeitig verfälschen können. Wie oben gezeigt, erscheint in diesem Fall jede Variable nur positiv oder nur negativ, und so ist die Formel erfüllen. Andernfalls fügen Sie $ | phi | $ Clausses des Formulars $ x lor y lor z $ hinzu, wobei $ x, y, z $ neue Variablen sind. In jeder Zuordnung sind entweder alle diese erfüllt oder alle nicht zufrieden. Da die ursprünglichen Klauseln nicht alle gleichzeitig gefälscht werden können (nach Annahme), kann die neue Formel nur dann halb befriedigt werden, wenn der ursprüngliche erfüllt ist.