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.