DNF-Equivalence Problem

Question

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 $NP-Hard$? If in $P$, how do we find an efficient algorithm and determine its complexity. How do we prove it if it's $NP-Hard$.

Answer 1

Hint:

DNF falsifiability is very similar to CNF satisfiability.

Let $l_i$ be the literals of DNF (i.e. $l_i$ might be $a_j$ or $\neg a_j$) then

\begin{align}\neg\Big((l_1 \land l_2 \land \ldots) &\lor (l_i \land \ldots) \lor \ldots\Big) \iff \\ \neg (l_1 \land l_2 \land \ldots) &\land \neg (l_i \land \ldots) \land \ldots \iff \\ (\neg l_1 \lor \neg l_2 \lor \ldots) &\land (\neg l_i \lor \ldots) \land \ldots \end{align}

I hope this helps $\ddot\smile$