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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.]