HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Is 2-DNF NP-complete?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
completednfstackoverflow

Problem

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

Solution

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

Context

StackExchange Computer Science Q#9927, answer score: 14

Revisions (0)

No revisions yet.