= 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:
$$
p=1-p^2\quad\Longrightarrow\quad\boxed{p=\frac{\sqrt5-1}{2}\approx0.618034.}
$$
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(\sqrt5)$ with polynomial bit complexity. The final deterministic assignment therefore has
$$
\boxed{\text{approximation ratio }\frac{\sqrt5-1}{2}.}
$$
This 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.
Back to article page
