= Solution
The decision problem is in <NP>: an assignment is a certificate, and counting its satisfied <clause> occurrences is polynomial in the input size.
Reduce <3-SAT> to it. For each of the $m$ original <clauses>, use the <seven-clause gadget for MAX-2SAT> with its three <literals> in place of $a,b,c$ and with a fresh auxiliary variable. Keep all ten <clause> occurrences per gadget, including any repeated occurrences across gadgets. Set the target to $k=7m$.
If the original formula is satisfiable, choose each auxiliary value as in part (a), giving seven satisfied <clauses> per gadget. Conversely, no gadget can exceed seven. If an assignment satisfies at least $7m$ <clauses> in total, every gadget must reach seven, so every original <clause> is satisfied by the original-variable assignment. The construction has $10m$ <clauses> and $m$ auxiliary variables, so is polynomial. Consequently \b[the decision version of <MAX-2SAT> is <NP-complete>.]
Back to article page
