Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Feb 25 '13 at 21:38

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

2  
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? –  Luke Mathieson Feb 26 '13 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. –  MGwynne Mar 6 '13 at 21:39

1 Answer 1

up vote 5 down vote accepted

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)

share|improve this answer

Your Answer

 
discard

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