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}}$.
Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?
cc.complexity theory;ds.algorithms;np hardness
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.