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

Let $r$ be the number of true values among $a,b,c$. Count the ten clause occurrences for the two choices of $d$. With $d=0$, the three positive singletons contribute $r$, the three negated-pair clauses contribute $3-\left(\genfrac{}{}{0ex}{}{r}{2}\right)$, and the last three clauses all hold. With $d=1$, the four singleton clauses contribute $r+1$, the negated pairs again contribute $3-\left(\genfrac{}{}{0ex}{}{r}{2}\right)$, and the last three contribute $r$. ThereforeThe original three-literal clause is satisfied exactly when $r\ge 1$, and then a value of $d$ satisfies exactly seven gadget clauses. If $r=0$, no choice reaches seven. Thus the required equivalence holds, and seven is also an upper bound for every assignment to the gadget. This is the seven-clause gadget for MAX-2SAT.

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.

Use the usual nonempty-clause convention and normalize repeated literals within a clause; tautologies are always satisfied. If empty clauses are admitted, discard them first: they contribute nothing to any assignment or to the optimum. Let $m$ be the resulting number of clause occurrences.

Assign independent fair truth values. A singleton clause is satisfied with probability $1/2$, a proper two-variable clause with probability $3/4$, and a tautology with probability one. By linearity of expectation, the expected number satisfied is at least $m/2$, hence at least $\mathrm{OPT}/2$.

To derandomize, use the method of conditional probabilities. After some variables have been fixed, let $F$ be the conditional expected number of satisfied clauses. For the next variable the two conditional expectations $F_0,F_1$ satisfy $F=(F_0+F_1)/2$. Fix the value with the larger expectation. This never decreases $F$. When all variables have been fixed, $F$ is the actual integer number of satisfied clauses, soCompute each conditional expectation by summing the probabilities of the clauses. Each has at most two variables, so its contribution is computed in constant time; scanning all clauses for each variable gives $O(nm)$ arithmetic operations. This is a polynomial-time approximation algorithm with approximation ratio $1/2$.

Apply the condition after the usual clause normalization, so each variable has at most one singleton clause. For a variable with such a clause, make its favored literal true with probability $p>1/2$; for other variables use a fair value. Make these choices independently. Then every singleton is satisfied with probability $p$.

Each literal of a proper two-variable clause is true with probability at least $1-p$. Independence bounds the probability that both are false by $p^2$, so the clause is satisfied with probability at least $1-p^2$. Tautologies have probability one. Thus the expected fraction satisfied is at least $\min (p,1-p^2)$. One term increases and the other decreases, so their intersection maximizes this bound:The method of conditional probabilities also works with these biased probabilities: before fixing a variable, the current expectation is the weighted average of its two conditional expectations, so choosing the larger cannot decrease it. Each clause contributes a constant-degree expression in $p$; since $p^2=1-p$, these expectations can be compared exactly in the fixed quadratic field $\mathbb{Q}(\sqrt{5})$ with polynomial bit complexity. The final deterministic assignment therefore hasThis is the golden ratio approximation for MAX-2SAT, under the stated restriction on normalized singleton clauses. Arbitrary conflicting singleton clauses do not admit the same independent-bias guarantee.