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.
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ For an in-deep analysis take a look to this paper "On Converting CNF to DNF" $\endgroup$– VorSep 12, 2012 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$– KavehSep 13, 2012 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$– vznSep 17, 2012 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 RicherbyJun 13, 2015 at 10:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
