If you want to make money online : Register now

# [Solved]: reducing Max3SAT to Max2sat

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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.

Try to understand how the existence of this gadget allows us to reduce MAX3SAT to MAX2SAT. Then either try to construct such a gadget, or look it up.