Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

migrated from Feb 19 '13 at 9:01

This question came from our site for theoretical computer scientists and researchers in related fields.

Please define the 2-DNF problem. – Vijay D Feb 19 '13 at 7:36
What are your own thoughts on the matter? – Raphael Feb 20 '13 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).

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.