12
$\begingroup$

In relation to the thread Proving that the conversion from CNF to DNF 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$).

Improve this question
$\endgroup$
5
  • $\begingroup$ You can go from any formula to a CNF which is satisfiable exactly when the original formula is in polynomial time. This is why CNF-SAT is NP-complete. Any SAT instance (an NP-complete problem) can be reduced to CNF-SAT in polynomial time. I think exactly translating it, not just preserving satisfiability will always sometimes yield an exponential explosion but I can't say this for sure. $\endgroup$
    – Jake
    Commented Apr 6, 2015 at 5:25
  • $\begingroup$ See en.wikipedia.org/wiki/Tseitin_transformation. Essentially, if you allow the introduction of auxiliary variables, you can do this transformation in poly-time (increasing the size of the formula at most linearly). $\endgroup$
    – jschnei
    Commented Apr 6, 2015 at 5:26
  • $\begingroup$ You'll need to decide whether you want to allow your conversion to introduce new variables or whether the converted formula must refer to the same set of variables (no new variables). This is a subtle point that has a dramatic effect on the answer. So, which do you want to ask about? $\endgroup$
    – D.W. ♦
    Commented Apr 6, 2015 at 5:26
  • $\begingroup$ @Jake You can go from any formula to an equisatisfiable CNF because CNF-SAT is NP-complete. It's not really "why" CNF-SAT is NP-complete: the usual proof that CNF-SAT is NP-complete doesn't involve translating arbitrary formulas to CNF; rather, it translates Turing machines into CNF formulas. $\endgroup$
    – David Richerby
    Commented Apr 6, 2015 at 14:04
  • $\begingroup$ To DW and others -- I had equisatisfiability in mind.. In this sense, it seems that equisatisfiability is just a reduction (in this case, to another Boolean formula). $\endgroup$
    – Martin Seymour
    Commented Apr 6, 2015 at 19:52

1 Answer 1

Reset to default
16
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ @Mehrdad, please don't use comments to ask new questions. We have a 'Ask Question' in the upper right for if you have a new question you want to ask. But, just a little tip... you might want to read the question at the top of this page before asking a new question... or, for that matter, posting this comment. I can't help but notice you've asked a question where the answer is found on the very same page as your question. $\endgroup$
    – D.W. ♦
    Commented Aug 21, 2016 at 3:03
  • $\begingroup$ @D.W.: Whoops, I actually saw the other post a little afterward and forgot to remove my comment here, sorry. Removed it now. $\endgroup$
    – user541686
    Commented Aug 21, 2016 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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