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