If you want to make money online : Register now

[Solved]: reducing Max3SAT to Max2sat

, , No Comments
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?

Asked By : Fayez Abdlrazaq Deab

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11739

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback