Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 37 / 6 / b

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 the decision version of MAX-2SAT is NP-complete.