# DNF to CNF conversion: Easy or Hard

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

• 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. – Jake Apr 6 '15 at 5:25
• 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). – jschnei Apr 6 '15 at 5:26
• 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? – D.W. Apr 6 '15 at 5:26
• @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. – David Richerby Apr 6 '15 at 14:04
• 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). – Martin Seymour Apr 6 '15 at 19:52