# Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

I have the following Equivalent DNF problem:

Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$

Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise.

$F_1$ and $F_2$ are equivalent if for all $(a_1,a_2,...a_n)∈\{0,1\}^n,F_1(a_1,a_2,...a_n)= F_2(a_1,a_2,...a_n).$

Is the DNF-Equivalence problem polynomial or in $\mathsf{NP\mbox{-Hard}}$? If in $P$, how do we find an efficient algorithm and determine its complexity. How do we prove it if it's $\mathsf{NP\mbox{-Hard}}$.

## 2 Answers

A special case of DNF equivalence is DNF tautology: Given a DNF formula $F$, is it satisfied for all assignments? This can be seen by setting $F_1 = F$ and $F_2$ to be a trivial tautology. CNF non-satisfiability is co-NP-complete. Negating the input formula turns a CNF formula into a DNF formula and vice versa and non-satisfiability into tautology. Thus, DNF tautology is co-NP-complete.

• Thanks for the answer. Does it mean the input values of $F_1$ and $F_2$ don't have any impact on the result(s) of the problem? – Jon Adam Oct 19 '13 at 6:41
• I am not sure if I understand your question correctly. What I meant is the following: First, DNF equivalence is in co-NP, as DNF non-equivalence is in NP. Second, DNF equivalence is co-NP-hard by the reduction sketched above: On input $F$, for which we want to decide whether the DNF formula $F$ is a tautology, we set $F_1=F$ and, for instance, $F_2 = a_1 \vee \lnot a_1$. Then $F_1$ and $F_2$ are equivalent if and only of $F$ is a tautology. Finally, DNF equivalence is unlikely to be NP-hard, because then we have a problem in co-NP that is NP-hard, which implies co-NP=NP. – Bodo Manthey Oct 19 '13 at 7:13

The DNF-Equivalence problem is a special case of the Formula Equivalence problem that is coNP-complete. If you assume that the DNF-Equivalence is $\mathsf{NP-hard}$ then, by definition, you have that every problem in $\mathsf{NP}$ reduces to the DNF-Equivalence problem that in turn implies $\mathsf{NP} \subseteq \mathsf{coNP}$

• Is the formatting as is or was it meant to be $F_1DNF$? – Jon Adam Oct 18 '13 at 7:11
• And is it in coNP-Complete in all cases? I mean with all kind of formulas. – Jon Adam Oct 18 '13 at 7:15
• Yes of course, it is that formatting. For all kind of formulas it is called FE problem (Formula Equivalence problem) that is a well-known coNP-complete problem. In other words DFE is a special case of FE and it is coNP-complete too. – Francesco Cris Oct 18 '13 at 7:28
• The problem with this answer is that $F_1 \leftrightarrow F_2$ is not a DNF-formula, and converting it to DNF can lead to a super-polynomial blowup. To show that the problem is in coNP one should rather quote the obvious direct coNP algorithm. – Jan Johannsen Oct 18 '13 at 7:42
• @JanJohannsen Does it mean the answer is wrong? – Jon Adam Oct 18 '13 at 7:51