Der Nachweis, dass die Konvertierung von CNF zu DNF NP-hart ist

20

Wie kann ich nachweisen, dass die Konvertierung von CNF zu DNF NP-hart ist?

Ich bitte nicht um eine Antwort, nur um ein paar Vorschläge, wie man es beweist.

complexity-theory np-hard satisfiability sat-solvers normal-forms jkjk
quelle
5
Eine eingehende Analyse finden Sie in diesem Artikel "Über die Konvertierung von CNF in DNF"
Vor dem
@ A.Schulz: Die ursprüngliche Definition in Steve Cooks Artikel definiert sie mithilfe von Cook-Reduktionen. Es scheint , dass die Reduktion verwendet werden , wenn allgemeine NP-Härte diskutieren en.wikipedia.org/wiki/NP-hard
Kaveh
CNF <-> DNF-Konvertierung ist keine Entscheidung, es muss eine Sprache sein. es ist eher eine Funktion mit Eingabe & Ausgabe & es muss in ein Entscheidungsproblem umgewandelt werden, um zu fragen, ob es in NP usw. ist Die NP-Vollversion des Entscheidungsproblems [falls es eines gibt] ist wahrscheinlich eine signifikante Vereinfachung. auch als Vors ref zeigt die tatsächliche Komplexität der CNF <-> DNF Umwandlung ist ein aktives Forschungsproblem ... note gibt es einige Ähnlichkeit mit Kompressionsalgorithmus Effizienz ...
VZN
2
@vzn Bei der Frage wird gefragt, ob es sich um NP -hard und nicht um NP -complete handelt. Dies bedeutet, dass die Mitgliedschaft bei NP nicht erforderlich ist, sodass dies kein Entscheidungsproblem darstellen muss.
David Richerby

Antworten:

18

Informell:

In DNF können Sie eine beliebige Klausel auswählen , um die Formel als wahr zu kennzeichnen. Dies bedeutet, dass ein DNF, der einem bestimmten CNF äquivalent ist, im Grunde eine Aufzählung aller Lösungen für Boolean-Sat auf dem CNF ist. Beachten Sie, dass es eine exponentielle Anzahl von Lösungen geben kann. Da das Lösen des Booleschen Sat für CNF für eine einzelne Lösung NP-vollständig ist, bedeutet das Umwandeln in DNF im Wesentlichen das Lösen für jede Lösung. Es ist also mindestens so schwer wie Boolesches SAT und damit NP-hart.

Realz Slaw
quelle