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.
CNF to DNF — conversion is NP Hard
4
$\begingroup$
algorithms
np-complete
-
2NP-hardness is usually formulated only for decision problems -- i.e. where the result is single bit rather than a data structure. What is the definition of NP-hardness you seek to apply to CNF-to-DNF? I think there are simple examples where the size of the DNF is exponential in the size of the CNF (or vice versa), but that does not really help you solve an _arbitrary_ NP problem, which is what NP-hard unsually requires. – 2011-12-14
-
0Im sorry I wasn't really clear in my question. Im trying show that the conversion from cnf-SAT to dnf-SAT is np-hard. – 2011-12-14
-
1That's doesn't really clear it up. What does it mean for such a _conversion_ to be NP-hard? Or are you asking for a polynomial-time reduction from DNF-SAT to CNF-SAT? I don't think there is one; satisfying a DNF is easy. – 2011-12-14
-
1@HenningMakholm: “NP-hardness is usually formulated only for decision problems”: That claim is too general to be true. Some people prefer to consider Turing reducibility by default (although I do not). NP-hardness under Turing reducibility applies to function problems or relation problems as well as to decision problems. – 2011-12-14
2 Answers
8
After converting a CNF formula to DNF I can solve the NP-complete problem SAT in linear-time by checking each DNF clause until I find one that does not contain a literal and its negation. This means that SAT is polynomial-time Turing reducible to CNF-to-DNF conversion. The existence of such a reduction is the definition of NP-hardness.
0
both the question and the other answer by KJ seems to assume that CNF ←→ DNF conversion can be done in P space, which is provably not the case. there are some formulas that lead to exponential blowup in size. its provably in a higher complexity class than P space. [not sure which one right now.] [suggest migrating this question to cs.se for better analysis there.]