Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

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

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

3  
For an in-deep analysis take a look to this paper "On Converting CNF to DNF" –  Vor Sep 12 '12 at 13:55
3  
@A.Schulz, NP-hard is used for other problem types also. –  Kaveh Sep 12 '12 at 20:26
    
@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 –  Kaveh Sep 13 '12 at 12:24
    
@Kaveh: Okay, You have convinced me. I withdraw my comments. –  A.Schulz Sep 13 '12 at 13:53
    
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... –  vzn Sep 17 '12 at 22:33

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.