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

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.