Problem Detail: In relation to the thread CNF to DNF — conversion is NP Hard (and a related Math thread): How about the other direction, from DNF to CNF? Is it easy or hard? On Page 2 of this paper, they seem to hint that both directions are equally hard when they say “We are interested in the maximal blow-up of size when switching from the CNF representation to the DNF representation (or vice versa)“. But DNF-SAT is in P and CNF-SAT is NP-complete. So given a DNF expression $phi_1$, there should be an equisatisfiable CNF expression $phi_2$ whose length is polynomial in the length of $phi_1$. And the $phi_1 to phi_2$ conversion can be done in poly time. Is this correct? Edit: Changed equivalent to equisatisfiable (that is, additional variables are allowed in $phi_2$).
Asked By : Martin Seymour
Answered By : D.W.
If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform. The resulting CNF formula will be equisatisfiable with the original DNF formula: the CNF formula will be satisfiable if and only if the original DNF formula was satisfiable. See also https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF. If you don’t want to allow introduction of additional variables, converting from DNF to CNF form is co-NP-hard. In particular, testing whether a DNF formula is a tautology is co-NP-hard. However, testing whether a CNF formula is a tautology can be done in polynomial time (you just check separately whether every clause is a tautology, which is easy as each clause is a disjunction of literals). Therefore, if you could convert from DNF form to CNF form in polynomial time, without introducing new variables, then you would obtain a polynomial-time algorithm for testing whether a DNF formula is a tautology — something which seems unlikely, given that we expect P is not equal to co-NP. Or, to put it another way, converting from DNF to CNF form without introducing additional variables is co-NP-hard. This is the difference between equivalence vs equisatisfiability. Equivalence requires the two formulas to have the same set of solutions (and thus does not allow introducing additional variables). Equisatisfiability only requires that either both formulas are satisfiable or both are unsatisfiable (and thus does allow introducing additional variables).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41070
