# Is 2-DNF NP-complete?

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

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

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.)

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.