4
$\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.

  • 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 2

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.]