Nachweis, dass die Umwandlung von CNF in DNF NP-Hard ist

1 answer
  • Informell:

    In DNF können Sie jede -Klausel als "wahr" auswählen, um die Formel auf "true" zu setzen. Dies bedeutet, dass eine DNF, die einer bestimmten CNF entspricht, im Wesentlichen eine Aufzählung aller Lösungen für boolesche Lösungen auf der CNF ist. Beachten Sie, dass es eine exponentielle Anzahl von Lösungen geben kann. Da das Lösen der booleschen Lösung für CNF für eine -Einzellösung NP-vollständig ist, bedeutet die Umwandlung in DNF im Wesentlichen das Lösen für jede -Lösung. Es ist also mindestens so schwer wie boolesches SAT und somit NP-hart.

    10 September 2012
    Jay Corbett