0
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jon Adam Oct 19 '13 at 6:41
  • $\begingroup$ 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. $\endgroup$ – Bodo Manthey Oct 19 '13 at 7:13
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is the formatting as is or was it meant to be $F_1DNF$? $\endgroup$ – Jon Adam Oct 18 '13 at 7:11
  • $\begingroup$ And is it in coNP-Complete in all cases? I mean with all kind of formulas. $\endgroup$ – Jon Adam Oct 18 '13 at 7:15
  • $\begingroup$ 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. $\endgroup$ – Francesco Cris Oct 18 '13 at 7:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Jan Johannsen Oct 18 '13 at 7:42
  • $\begingroup$ @JanJohannsen Does it mean the answer is wrong? $\endgroup$ – Jon Adam Oct 18 '13 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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