Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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
2  
NP-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. – Henning Makholm Dec 14 '11 at 15:49
Im sorry I wasn't really clear in my question. Im trying show that the conversion from cnf-SAT to dnf-SAT is np-hard. – sammy Dec 14 '11 at 16:06
1  
That'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. – Henning Makholm Dec 14 '11 at 16:13
@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. – Tsuyoshi Ito Dec 14 '11 at 18:42

1 Answer

up vote 6 down vote

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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.