# Why is MAX-2SAT not in P?

Max-2-SAT is defined as follows. We are given a 2-CNF formula and a bound k, and asked to find an assignment to the variables that satisfies at least k of the clauses.

I can understand the trick used to prove 2-SAT is in P. You use get a contradiction by using unit propagation. But, I was wondering why does MAX 2-SAT escape this.

Also, I find it hard to believe this is NP-complete. Certainly, what is the problem that causes it to blow up.

Why wouldn't an algorithm like this work. Given a 2-SAT expression. Find it's length, which we can do in P. Need to check if there is at least k of the clauses.

So we just check $\binom n k$ posibilities and run like Horn algorithm on each sub expression of the n 2-SAT expression. Surely, where is the problem as we are just running a P algorithm a polynomial amount of time.

So I'm very confused. Sort of similar problem I have factorization and if that is in P or NP.

• Just to clarify (considering the title question), you're actually comfortable with the fact that MAX-2-SAT is in NP, just weren't sure why it was NP-complete? Feb 26, 2013 at 2:13
• Actually, it's easier to see 2-SAT being in P due to the fact that all resolvents are of size <=2 and so there are most quadratically many resolvents, in which you can then check for the empty clause (this is basically computing the transitive closure of the directed graph given by all the clauses). 2-SAT can't always be solved by UCP, unless you use some additional lookahead - for example consider $(\neg a \vee \neg b) \wedge (\neg a \vee b) \wedge (a \vee \neg b) \wedge (a \vee b)$, UCP will do nothing but it is unsatisfiable. Mar 6, 2013 at 21:39

Observe that the expression ${n\choose k}$ may be exponential in $n$ (e.g. if $k=n/2$).