patternModerate
Proving that the conversion from CNF to DNF is NP-Hard
Viewed 0 times
conversionprovingthehardcnfthatfromdnf
Problem
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.
I'm not asking for an answer, just some suggestions about how to go about proving it.
Solution
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.
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.
Context
StackExchange Computer Science Q#3513, answer score: 18
Revisions (0)
No revisions yet.