For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an example, only how to do it theoreticaly and since I'm new to the topic I can't really make much progress. I don't fully understand it.

Thanks in advance for all of the comments trying to help.

  • $\begingroup$ A simple proof can be found in this paper (Theorem 1.1 on page 240) It also shows an explicit construction of the MAX 2-SAT instance from the 3-SAT instance. $\endgroup$ – Reinhard Meier Feb 10 '19 at 14:40

Assume you start with a 3-SAT instance with $m$ clauses. The usual reduction shows that each 3-CNF clause of a 3-SAT instance can be transformed into ten 2-CNF clauses such that a satisfying assignment to the 3-CNF clause can satisfy at most seven of the 2-CNF clauses. An unsatisfying assignment for the clause can satisfy at most only six of the produced 2-CNF clauses.

So after doing the transformation for all $m$ of the 3-CNF clauses the resulting MAX-2-SAT instance can have $7m$ of its clauses satisfied iff the original 3-CNF formula is satisfiable. Since determining the satisfiability of a 3-CNF formula is NP-hard, MAX-2-SAT must be NP-hard as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.