20
$\begingroup$

How can I prove that the conversion from CNF to DNF is NP-Hard?

I'm not asking for an answer, just some suggestions about how to go about proving it.

$\endgroup$

migrated from stackoverflow.com Sep 12 '12 at 12:52

This question came from our site for professional and enthusiast programmers.

  • 5
    $\begingroup$ For an in-deep analysis take a look to this paper "On Converting CNF to DNF" $\endgroup$ – Vor Sep 12 '12 at 13:55
  • $\begingroup$ @A.Schulz: the original definition in Steve Cook's paper defines it using Cook reductions. It seems that is the reduction used when discussing general NP-hardness en.wikipedia.org/wiki/NP-hard $\endgroup$ – Kaveh Sep 13 '12 at 12:24
  • $\begingroup$ CNF <-> DNF conversion is not a decision, reqd for it to be a language. its more a function with input & output & it has to be converted to a decision problem to ask if its in NP etc. think that the non decision problem has been proven to lead to exponential blowup in size [eg in Vors ref] therefore an NP complete version of the decision problem [if one is out there] is probably a significant simplification. also as Vors ref shows the actual complexity of CNF<->DNF conversion is an active research problem... note there is some similarity to compression algorithm efficiency... $\endgroup$ – vzn Sep 17 '12 at 22:33
  • 2
    $\begingroup$ @vzn The question asks if it's NP-hard, not NP-complete. This means that membership of NP is not required so it doesn't have to be a decision problem. $\endgroup$ – David Richerby Jun 13 '15 at 10:25
18
$\begingroup$

Informally:

In DNF, you can pick any clause to be true, to make the formula true. This means that a DNF that is equivalent to a certain CNF, is basically an enumeration of all the solutions to boolean sat on the CNF. Note, there can be an exponential number of solutions. Since solving boolean sat for CNF for a single solution is NP-complete, converting to DNF essentially means solving for every solution. So it is at least as hard as Boolean SAT, and is thus NP-hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.