<p>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.</p>

CC BY-SA 3.0
2013-10-19T06:41:31.963Z
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
CC BY-SA 3.0
2013-10-19T07:13:10.850Z
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
CC BY-SA 3.0
2013-10-18T09:42:05.110Z
2013-10-19T07:04:58.797Z
2013-10-19T07:04:58.797Z
Bodo Manthey
<p>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} $</p>

CC BY-SA 3.0
2013-10-18T07:11:22.250Z
Is the formatting as is or was it meant to be $F_1DNF$?
Jon Adam
CC BY-SA 3.0
2013-10-18T07:15:12.413Z
And is it in coNP-Complete in all cases? I mean with all kind of formulas.
Jon Adam
CC BY-SA 3.0
2013-10-18T07:28:27.397Z
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
CC BY-SA 3.0
2013-10-18T07:42:02.340Z
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
CC BY-SA 3.0
2013-10-18T07:51:41.163Z
@JanJohannsen Does it mean the answer is wrong?
Jon Adam
CC BY-SA 3.0
2013-10-18T07:53:51.103Z
By the last comment, it should be enough to consider just the TAUT problem in the above answer (and not TAUT-DNF) that is coNP-complete too and considering $F, F_1, F_2 $ as DNF formulas
Francesco Cris
CC BY-SA 3.0
2013-10-18T07:57:43.017Z
No, just the argument does not work. 
1) shows that the problem is coNP-hard, and one can show that it is in coNP by the obvious algorithm: for very assignment check that bothe formulas yield th esame value.
Jan Johannsen
CC BY-SA 3.0
2013-10-18T08:26:38.710Z
@JonAdam, yes the reduction in my answer is not right, my apologies.
Francesco Cris
CC BY-SA 3.0
2013-10-18T09:00:24.633Z
@FrancescoCris: Would you mind making that edit?
Jon Adam
CC BY-SA 3.0
2013-10-18T09:04:58.373Z
@JanJohannsen: Or would you mind adding that to the answer if you don't mind.
Jon Adam
CC BY-SA 3.0
2013-10-18T06:51:41.533Z
2013-10-18T09:24:48.637Z
2013-10-18T09:24:48.637Z
Francesco Cris
<p>I have the following Equivalent DNF problem:</p>

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

<p>Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise.</p>

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

<p>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}}$.</p>

<cc.complexity-theory><ds.algorithms><np-hardness>
Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?
Jon Adam
# Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

(Asked by: username_0 on 2013-10-18)

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

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness

---

## 2 answers

### Answer by username_1 on 2013-10-18. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  

---

### Answer by username_2 on 2013-10-18. Score: 0

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} $

> **Comments:**
> **username_0**: Is the formatting as is or was it meant to be $F_1DNF$?  
> **username_0**: And is it in coNP-Complete in all cases? I mean with all kind of formulas.  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: @JanJohannsen Does it mean the answer is wrong?  
> **username_2**: By the last comment, it should be enough to consider just the TAUT problem in the above answer (and not TAUT-DNF) that is coNP-complete too and considering $F, F_1, F_2 $ as DNF formulas  
> **username_3**: No, just the argument does not work.  1) shows that the problem is coNP-hard, and one can show that it is in coNP by the obvious algorithm: for very assignment check that bothe formulas yield th esame value.  
> **username_2**: @JonAdam, yes the reduction in my answer is not right, my apologies.  
> **username_0**: @FrancescoCris: Would you mind making that edit?  
> **username_0**: @JanJohannsen: Or would you mind adding that to the answer if you don't mind.  

---

