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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Oct 19, 2013 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
    Commented Oct 19, 2013 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} $

Improve this answer
$\endgroup$
10
  • $\begingroup$ Is the formatting as is or was it meant to be $F_1DNF$? $\endgroup$
    – Jon Adam
    Commented Oct 18, 2013 at 7:11
  • $\begingroup$ And is it in coNP-Complete in all cases? I mean with all kind of formulas. $\endgroup$
    – Jon Adam
    Commented Oct 18, 2013 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
    Commented Oct 18, 2013 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
    Commented Oct 18, 2013 at 7:42
  • $\begingroup$ @JanJohannsen Does it mean the answer is wrong? $\endgroup$
    – Jon Adam
    Commented Oct 18, 2013 at 7:51

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.