Transformieren Sie einen CNF in einen äquivalenten 3-CNF, der für dieselben Variablen definiert ist

(Ich habe diese Frage vor zehn Tagen auf CS gepostet , seitdem keine Antwort mehr - also poste ich sie hier.)

Jede CNF-Formel kann in Polynomzeit unter Verwendung neuer Variablen in eine 3-CNF-Formel umgewandelt werden. Es ist nicht immer möglich, wenn neue Variablen nicht zulässig sind (nehmen Sie zum Beispiel die Einzelklauselformel: ). $(x_1 \lor x_2 \lor x_3 \lor x_4)$

Definieren wir das Problem (SAT bis 3-SAT): Gegeben ist , eine CNF-Formel. Ist es möglich, in einen äquivalenten 3-CNF umzuwandeln, der auf denselben Variablen wie ? - wobei "äquivalent" mit demselben Modellsatz bedeutet. $F$ $F$ $F$

Was ist die Komplexität dieses Problems?

cc.complexity-theory complexity-classes sat Xavier Labouze
quelle

Mit Äquivalent meinen Sie gleichwertig, nehme ich an?

Jan Johannsen

Eher "mit dem gleichen Satz von Modellen".

Xavier Labouze

fyi tseitin Transformation ist der Name für die Transformation von -SAT bis 3-SAT unter Verwendung von zusätzlichen Vars. Ihre Frage scheint so etwas wie die Frage nach der Existenz eines Komprimierungsalgorithmus für SAT zu sein. Es hört sich so an, als wollten Sie die gleichen Lösungen, indem Sie die Klauseln auf 3 oder weniger Variablen kürzen. von EE bezieht sich dies auf die Aufzählung aller Zwischenzeiten und das Auffinden minimaler Deckungen und die Frage, ob welche vorhanden sind, die den Kriterien entsprechen (in diesem Fall alle Klauseln 3 oder weniger vars). es scheint eine potenziell hohe Komplexität zu haben.

n

$n$

VZN

Vielleicht ist es Co-NP-vollständig: Wählen Sie eine 3CNF-Formel , erstellen Sie eine neue Formel mit 4 neuen Variablen . hat eine 3CNF-äquivalente Formel für dieselben Variablen, wenn und nur wenn nicht erfüllt werden kann.

φ = C_{1} \land . . . \land C_{n}

$\varphi = C_1 \land ... \land C_n$

φ^{'} = (y_{1} \lor y_{2} \lor y_{3} \lor y_{4}) \land C_{1} \land . . . \land C_{n}

$\varphi' = (y_1 \lor y_2 \lor y_3 \lor y_4) \land C_1 \land ... \land C_n$

y_{1}, . . ., y_{4}

$y_1,...,y_4$

φ^{'}

$\varphi'$

φ

$\varphi$

Marzio De Biasi

@MarzioDeBiasi. Nett ! Ich bin mir jedoch nicht sicher, ob es ausreicht, die Vollständigkeit des Co-NP zu beweisen (irgendwie erwarte ich eine höhere Komplexität, aber es ist nur eine Intuition ...)

Xavier Labouze,

(Aus dem obigen Kommentar) Das Problem scheint coNP-schwer zu sein; Die einfache Reduktion stammt von 3CNF-UNSAT (das coNP-vollständig ist): Wenn eine 3CNF-Formel , erweitern Sie sie um eine neue Klausel mit 4 neuen Variablen: $\varphi = C_1 \land ... \land C_m$

φ^{'} = (y_{1} \lor y_{2} \lor y_{3} \lor y_{4}) \land C_{1} \land . . . \land C_{m}

$\varphi' = (y_1 \lor y_2 \lor y_3 \lor y_4) \land C_1 \land ... \land C_m$

$\varphi'$ hat eine äquivalente 3CNF-Formel, die genau dann für dieselben Variablen definiert ist, wenn die ursprüngliche Formel zufriedenstellend ist. $\varphi$

( ) Die 3CNF-Formel entspricht $\Leftarrow$ $(y_1 \lor y_2 \lor y_3) \land (y_1 \lor y_2 \lor y_4) \land C_1 \land ... \land C_m$ $\varphi'$

( ) Angenommen, hat eine äquivalente 3CNF-Formel und ist erfüllbar. Wählen Sie eine zufriedenstellende Zuordnung von und vereinfachen Sie sowohl als auch indem Sie die Variablen durch die entsprechende Wahrheit ersetzen Werte . Wir erhalten was genau dann , wenn erfüllt werden kann (beide enthalten nur Variablen ). Offensichtlich $\Rightarrow$ $\varphi'$ $\varphi''$ $\varphi$ $X = \langle \dot{x}_1,...,\dot{x}_n \rangle$ $\varphi$ $\varphi'$ $\varphi''$ $x_i$ $\dot{x}_i$ $\varphi'_X$ $\varphi''_X$ $y_i$ $\varphi'_X = (y_1 \lor y_2 \lor y_3 \lor y_4)$ . Jede Klausel von enthält höchstens drei Variablen, sodass wir eine davon auswählen können, z. B. , und daraus eine zufriedenstellende Zuordnung für : erstellen können was für keine zufriedenstellende Zuordnung ist , was zu a führt Widerspruch. $\varphi''_X$ $(y_1 \lor \lnot y_2 \lor y_3)$ $\varphi'$ $\langle y_1=false, y_2=true, y_3=false,y_4=true,\dot{x}_1,...,\dot{x}_n \rangle$ $\varphi''$

Marzio De Biasi
quelle

Tks für die Antwort. Ich verstehe das : Ich hätte gesagt, wenn unbefriedigend ist, ist es auch , was dann der leeren Klausel (Größe 0) entspricht. Wenn Sie für ) nur denken, wenn , dann ist äquivalent zu ...

(\Leftarrow)

$(\Leftarrow)$

φ

$\varphi$

φ^{'}

$\varphi'$

(\Rightarrow

$(\Rightarrow$

φ = (x \lor \neg x)

$\varphi = (x \lor \lnot x)$

(y_{1} \lor y_{2} \lor y_{3} \lor y_{4}) \land (x \lor \neg x)

$(y_1 \lor y_2 \lor y_3 \lor y_4) \land (x \lor \lnot x)$

(y_{1} \lor y_{2} \lor x) \land (y_{3} \lor y_{4} \lor \neg x)

$(y_1 \lor y_2 \lor x)\land (y_3 \lor y_4 \lor \lnot x)$

Xavier Labouze

@ XavierLabouze: Ja, dein scheint besser zu sein. In ( gehe ich davon aus, dass es ein äquivalentes 3CNF , und leite dann einen Widerspruch aus der Annahme ab, dass das ursprüngliche erfüllbar ist. Glaubst du, es ist falsch?

(\Leftarrow)

$(\Leftarrow)$

\Rightarrow)

$\Rightarrow)$

φ^{'}

$\varphi'$

φ

$\varphi$

Marzio De Biasi

Sie haben Recht - ich habe mich geirrt, als ich angegeben habe, dass die gleichen Modelle hat wie .

(y_{1} \lor y_{2} \lor y_{3} \lor y_{4}) \land (x \lor \neg x)

$(y_1 \lor y_2 \lor y_3 \lor y_4) \land (x \lor \lnot x)$

(y_{1} \lor y_{2} \lor x) \land (y_{3} \lor y_{4} \lor \neg x)

$(y_1 \lor y_2 \lor x)\land (y_3 \lor y_4 \lor \lnot x)$

Xavier Labouze

Haben Sie bemerkt, dass gleich ? Können Sie dies erklären: "Wir erhalten das genau dann , wenn erfüllt werden kann", als Sie hinzufügen "(beide enthalten nur Variablen )", wie können Sie sicher sein, dass der ist nur enthalten ? Ich verstehe auch die Schlussfolgerung nicht. Haben Sie bewiesen, dass das Hinzufügen einer 4-Variablen-Klausel zu 3-cnf aus denselben Variablen coNP-Complete ist?

(y_{1} \lor y_{2} \lor y_{3}) \land (y_{1} \lor y_{2} \lor y_{4})

$(y_1 \lor y_2 \lor y_3) \land (y_1 \lor y_2 \lor y_4)$

(y_{1} \lor y_{2}) \land (y_{3} \lor y_{4})

$(y_1 \lor y_2) \land (y_3 \lor y_4)$

φ_{X}^{'}

$\varphi'_X$

φ_{X}^{″}

$\varphi''_X$

y_{i}

$y_i$

y_{i}

$y_i$

Ilya Gazman

φ_{1} = (y_{1} \lor y_{2} \lor y_{3}) \land (y_{1} \lor y_{2} \lor y_{4})

$\varphi_1 = (y_1 \lor y_2 \lor y_3) \land (y_1 \lor y_2 \lor y_4)$ und sind gleichwertig, aber nicht gleichwertig (gleich) Satz von Modellen): y1 = F, y2 = F, y3 = T, y4 = T ist ein gültiges Modell für jedoch nicht für . In der Frage sprechen wir über äquivalente Formeln. Der Beweis beruht auf der Tatsache, dass nicht den gleichen Satz von Modellen von 3CNF-Formeln haben kann.

φ_{2} = (y_{1} \lor y_{2}) \land (y_{3} \lor y_{4})

$\varphi_2 = (y_1 \lor y_2) \land (y_3 \lor y_4)$

φ_{1}

$\varphi_1$

φ_{2}

$\varphi_2$

(y_{1} \lor y_{2} \lor y_{3} \lor y_{4})

$(y_1 \lor y_2 \lor y_3 \lor y_4)$

Marzio De Biasi

Transformieren Sie einen CNF in einen äquivalenten 3-CNF, der für dieselben Variablen definiert ist

Antworten: