Reduction from 3-SAT to MAX 2SAT

Question

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.

Answer 1

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 if an assignment to the 3-CNF clause satisfies it, then exactly seven of the 2-CNF clauses can be satisfied. If an assignment for the clause does not satisfy it, then exactly six of the produced 2-CNF clauses can be satisfied.

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.