Why is MAX-2SAT not in P?
-
16-10-2019 - |
Pergunta
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.
Solução
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)