Ist Monotone 3-Sat mit genau 3 verschiedenen Variablen nicht unbeheilig?

Question

Ich habe die folgende SAT-Variante gegeben:

Angesichts einer Formel F in CNF, in der jede Klausel C genau 3 verschiedene Literale aufweist, und für jeden C in F sind entweder alle Literalen positiv oder alle Literaturen negiert. Beispiel:

$ F= (X_1 \ Vee X_2 \ Vee X_4) \ wedge (\ neg x_2 \ vee \ neg x_3 \ vee \ neg x_4) \ wedge (x_3 \ vee x_4 \ Vee x_5) $

ist diese Variation von sat traktablierbar?

meine Ergebnisse bisher:

Ich vermute, das Problem ist np-komplett und daher nicht traktabler. Somit möchte ich eine Poly-Reduktion von 3-Sat auf die oben beschriebene Variante durchführen.

Eine beliebige 3-Sat-Formel kann in Monoton 3-Sat umgewandelt werden.

Nachfolgendes Beispiel:

$ c_1= (x_1 \ vee x_2 \ vee \ neg x_3) $ und definieren $ z_3 $ mit $ \ neg x_3 \ leftrightarrow z_3 $ und $ X_3 \ LEFTRIGHTARROW \ NEG Z_3 $ das gleichwertig ist zu $ (x_3 \ vee z_3) \ wedge (\ neg x_3 \ vee \ neg z_3) $ .

Daraus erfahren wir die monotone Form von $ c_1 $ von

$ (x_1 \ vee x__2 \ vee \ neg x_3) \ leftrightarrow (x_1 \ vee x_2 \ vee z_3) \ wedge (x_3 \ vee z_3) \ wedge (\ neg x_3) \ vee \ neg z_3) $

Durch Anwenden dieser Transformation an alle Klauseln bekomme ich eine monotone 3-sat-Formel, die gleichermaßen erfüllt ist.

Meine Reduktion erzeugt zusätzliche 2 Klauseln mit 2 Literalen für jede Nicht-Monoton-Klausel, aber wie bekomme ich nur Monoton-Klauseln mit genau 3 verschiedenen Literalen?

Answer 1

Ich werde versuchen, jetzt meine eigene Frage zu beantworten, und freue mich über etwas Fütterung in Bezug auf die Kreektheit.

Wie in der oben diskutierten Frage, die von Kyle Jones diskutiert und aufwiesen, können wir willkürliche 3-Sat-Formeln zu Monoton-3-Sat-Formeln reduzieren.

Beispiele A Klausel $ C= (X_1 \ Vee X_2 \ Vee \ neg x_3) $ kann in konvertiert werden> $ C '(X_1 \ Vee X_2 \ Vee Z_3) \ wedge (z_3 \ vee x_3) \ wedge (\ neg z_3 \ vee \ neg x_3) $ . Man kann prüfen, ob $ C $ erfüllt ist $ C '$ ist auch erfüllt und wenn $ C $ ist nicht erfüllt $ c '$ ist auch nicht erfüllt.

Der nächste Schritt besteht darin, alle Klauseln mit weniger als 3 Literalen in Klauseln mit genau 3 verschiedenen Literalen umzuwandeln.

Nehmen Sie daher zum Beispiel $ c_1= (x_1 \ vee x_2) $ und wandeln Sie es auf $ c_1 '= ( x_1 \ vee x_2 \ vee y_1) \ wedge (x_1 \ vee x_2 \ vee y_2) \ wedge (x_1 \ vee x_2 \ vee y_3) \ wedge (\ neg y_1 \ vee \ neg y_2 \ vee \ neg y_3) $ dann erneut, wenn $ c_1 $ erfüllt ist $ c_1 '$ ist auch erfüllt und wenn $ C_1 $ ist nicht erfüllt $ c_1 '$ ist auch nicht erfüllt. Dasselbe kann für den negativen Fall erfolgen, dh $ c_2= (\ neg x_1 \ vee \ neg x_2) $ kann in $ C_2 '= (\ neg x_1 \ vee \ neg x_2 \ vee \ neg u_1) \ wedge (\ neg x_1 \ vee \ neg x_2 \ vee \ neg \ neg \ neg x_2 \ vee \ neg u_2) \ wedge (\ neg x_1 \ vee \ neg x_2 \ vee \ neg u_3) \ wedge (u_1 \ vee u_2 \ vee u_3) $

Durch Anlegen der beiden Transformationen kann man eine beliebige 3-Sat-Instanz in eine Monoton-3-SAT-Instanz mit genau 3 verschiedenen Literalen umwandeln. Wie leicht über den Transformationen zu sehen ist, weisen die Umwandlungen auf Polynomkomplexität aufweisen. Seit 3-Sat ist NP-Hard die Reduktion, die Aswell np-hart sein muss.