4
$\begingroup$

I want to know whether the 2-DNF problem is NP-complete or not? If it is NP-complete, can anyone provide a proof?

$\endgroup$
2
  • 3
    $\begingroup$ Please define the 2-DNF problem. $\endgroup$
    – Vijay D
    Feb 19, 2013 at 7:36
  • 3
    $\begingroup$ What are your own thoughts on the matter? $\endgroup$
    – Raphael
    Feb 20, 2013 at 6:56

3 Answers 3

14
$\begingroup$

If you are referring to the problem of deciding whether a formula given in 2-DNF form is satisfiable, then it is in $P$, as well as general DNF satisfiability. Indeed, such a formula is satisfiable iff there is a clause that does not contain an inner contradiction. That is, a clause that does not contain both $p$ and $\neg p$ for some atomic proposition $p$. This can be checked in linear time.

Perhaps you are referring to 2-CNF? (Which is also in $P$, but it's less trivial.)

$\endgroup$
6
$\begingroup$

An additional note to Shaull's answer.

Checking if a DNF formula $\phi$ is valid (i.e. is a tautology) is co-NP-complete.

Indeed a formula $\phi$ is valid if and only if its negation is not satisfiable. But if you negate a DNF formula and apply De Morgan's laws you get a CNF formula. So the problem is equivalent to CNF unsatisfiability.

But if you restrict to 2-DNF, the validity can be checked in polynomial time because the corresponding negated formula is equivalent to the (un)satisfiability of a 2-CNF formula (that can be checked in polynomial time).

$\endgroup$
1
$\begingroup$

#2SAT and #2DNF are both #P-complete however. #2SAT can be converted to #2DNF by taking a not of the equation and applying DeMorgans law. If you have n literals then #2SAT=2^n-#2DNF, you subtract the total possible solutions from the number of unsatisfiable to get the number of satisfiable equations. #2CNF reduces to #3CNF which reduces to #3CNF-balanced which reduces to the (-1,0,1) permanent which reduces to the {0,...,m} permanent which reduces to the (0, 1) permanent which is #P-complete per Valiant. You could also likewise reduce #3CNF to #3DNF and then #3DNF-monotone (or convert to monotone while still at #3CNF) then reduce further to #2SAT-monotone. And just like that you can circle around from #2SAT to #2SAT-monotone. Regardless all of these problems and more are #P.

$\endgroup$

Your Answer

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