Umwandlung von DNF in CNF: Einfach oder schwer

In Bezug auf den Thread Nachweis, dass die Konvertierung von CNF zu DNF NP-Hard ist (und ein verwandter Math-Thread ):

Wie wäre es mit der anderen Richtung, von DNF zu CNF? Ist es einfach oder schwer?

Auf Seite 2 dieses Papiers scheinen sie darauf hinzudeuten, dass beide Richtungen gleich schwer sind, wenn sie sagen " Wir sind an der maximalen Vergrößerung der Größe interessiert, wenn wir von der CNF-Darstellung zur DNF-Darstellung wechseln (oder umgekehrt) ".

Aber DNF-SAT ist in P und CNF-SAT ist NP- vollständig. Bei einem DNF-Ausdruck sollte es also einen nicht zufriedenstellenden CNF-Ausdruck dessen Länge in der Länge von polynomisch ist . Die Konvertierung von kann in Poly-Zeit erfolgen. Ist das richtig? $\phi_1$ $\phi_2$ $\phi_1$ $\phi_1 \to \phi_2$

Bearbeiten: Äquivalent zu gleichwertig geändert ( dh zusätzliche Variablen sind in zulässig ). $\phi_2$

complexity-theory logic satisfiability normal-forms Martin Seymour
quelle

Sie können von einer beliebigen Formel zu einem CNF wechseln, der genau dann erfüllt werden kann, wenn sich die ursprüngliche Formel in Polynomzeit befindet. Deshalb ist CNF-SAT NP-vollständig. Jede SAT-Instanz (ein NP-vollständiges Problem) kann in Polynomzeit auf CNF-SAT reduziert werden. Ich denke, eine genaue Übersetzung, nicht nur die Wahrung der Erfüllbarkeit, führt manchmal zu einer exponentiellen Explosion, aber ich kann das nicht mit Sicherheit sagen.

Jake

Siehe en.wikipedia.org/wiki/Tseitin_transformation . Wenn Sie die Einführung von Hilfsvariablen zulassen, können Sie diese Transformation im Wesentlichen in Poly-Zeit durchführen (wobei die Größe der Formel höchstens linear erhöht wird).

Jschnei

Sie müssen entscheiden, ob Sie mit Ihrer Konvertierung neue Variablen einführen möchten oder ob sich die konvertierte Formel auf denselben Variablensatz beziehen muss (keine neuen Variablen). Dies ist ein subtiler Punkt, der sich dramatisch auf die Antwort auswirkt. Also, worüber möchten Sie fragen?

@Jake Sie können von jeder Formel zu einem nicht zufriedenstellenden CNF wechseln, da CNF-SAT NP-vollständig ist. Es ist nicht wirklich "warum" CNF-SAT NP-vollständig ist: Der übliche Beweis, dass CNF-SAT NP-vollständig ist, beinhaltet nicht die Übersetzung beliebiger Formeln in CNF; Vielmehr werden Turing-Maschinen in CNF-Formeln übersetzt.

David Richerby

Für DW und andere - ich hatte Gleichheit im Sinn. In diesem Sinne scheint Gleichheit nur eine Reduktion zu sein (in diesem Fall auf eine andere Boolesche Formel).

Martin Seymour

Antworten:

Wenn Sie bereit sind, zusätzliche Variablen einzuführen, können Sie mithilfe der Tseitin-Transformation in Polynomzeit von DNF- in CNF-Form konvertieren . Die resultierende CNF-Formel ist mit der ursprünglichen DNF-Formel gleichwertig: Die CNF-Formel ist nur dann erfüllbar, wenn die ursprüngliche DNF-Formel erfüllt werden konnte. Siehe auch https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF .

Wenn Sie die Einführung zusätzlicher Variablen nicht zulassen möchten, ist die Konvertierung von DNF- in CNF-Form co-NP-schwer. Insbesondere ist das Testen, ob eine DNF-Formel eine Tautologie ist, co-NP-hart. Das Testen, ob eine CNF-Formel eine Tautologie ist, kann jedoch in Polynomzeit durchgeführt werden (Sie prüfen nur separat, ob jede Klausel eine Tautologie ist, was einfach ist, da jede Klausel eine Disjunktion von Literalen ist). Wenn Sie also in Polynomzeit von der DNF-Form in die CNF-Form konvertieren könnten, ohne neue Variablen einzuführen, würden Sie einen Polynomzeitalgorithmus erhalten, mit dem Sie testen können, ob eine DNF-Formel eine Tautologie ist - etwas, das angesichts unserer Erwartung unwahrscheinlich erscheint P ist nicht gleich co-NP. Oder anders ausgedrückt: Die Konvertierung von DNF- in CNF-Form ohne Einführung zusätzlicher Variablen ist co-NP-schwer.

Dies ist der Unterschied zwischen Äquivalenz und Gleichzufriedenheit . Für die Äquivalenz müssen die beiden Formeln denselben Lösungssatz haben (und können daher keine zusätzlichen Variablen einführen). Gleichheit erfordert nur, dass entweder beide Formeln erfüllt werden oder beide nicht erfüllt sind (und somit die Einführung zusätzlicher Variablen ermöglicht).

DW
quelle

@Mehrdad, bitte benutze keine Kommentare, um neue Fragen zu stellen. Wir haben oben rechts eine Frage stellen, wenn Sie eine neue Frage haben, die Sie stellen möchten. Aber nur ein kleiner Tipp ... Vielleicht möchten Sie die Frage oben auf dieser Seite lesen, bevor Sie eine neue Frage stellen ... oder diesen Kommentar veröffentlichen. Ich kann nicht anders, als zu bemerken, dass Sie eine Frage gestellt haben, deren Antwort sich auf derselben Seite wie Ihre Frage befindet.

@ DW: Hoppla, ich habe den anderen Beitrag ein wenig später gesehen und vergessen, meinen Kommentar hier zu entfernen, sorry. Entfernte es jetzt.

user541686