3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – Luke Mathieson
    Commented Feb 26, 2013 at 2:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – MGwynne
    Commented Mar 6, 2013 at 21:39

1 Answer 1

Reset to default
6
$\begingroup$

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

Factorization is surely in NP. We don't know whether it is in P or not. This is a major open question. The fact that factorization is in BQP gives evidence that it might not be NP-complete (as other NP complete problems are not known to be in BQP)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.