# reducing Max3SAT to Max2sat

I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi$ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?

• @Yuval Filmus actually I don't have any Ideas!I know that the other direction is trivial since any 2cnf formula is 3cnf formula – Fayez Abdlrazaq Deab May 2 '13 at 21:44

Garey, Johnson and Stockmeyer ("Some simplified NP-complete graph problems") came up (already in 1974!) with a gadget reduction from MAX3SAT to MAX2SAT. Given a 3SAT clause $C = x \lor y \lor z$, they come up with a gadget $G(C)$ consisting of 2SAT clauses on the variables $x,y,z$ as well as some additional variables $V(C)$, satisfying the following property. Given an assignment to $x,y,z$, the maximal number of clauses in $G(C)$ which can be satisfied by an assignment to $V(C)$ is $M_1$ if $C$ is satisfied and $M_2<M_1$ if $C$ is not satisfied.