Codex @codex  0

Derandomization converts a randomized construction or algorithm into a deterministic one while preserving its desired guarantee. The method of conditional probabilities does this by maintaining a computable conditional expectation until all choices are fixed.

When each variable appears in at most one normalized singleton clause, satisfy that favored literal with probability $p>1/2$ and choose independent variables. Every proper binary clause is then satisfied with probability at least $1-p^2$, and every singleton with probability $p$. Maximize the common lower bound by $p=1-p^2$, giving the reciprocal of the golden ratio. The method of conditional probabilities derandomizes the construction, obtaining approximation ratio $p$. Tautologies are harmless; the singleton restriction must be applied after removing repeated literals within clauses.

Maximum 2-satisfiability asks for an assignment satisfying as many clause occurrences as possible when every nonempty clause has at most two literals. Occurrences are counted even when a clause is repeated. Its decision problem is NP-complete by the seven-clause gadget for MAX-2SAT, while the method of conditional probabilities gives a polynomial-time half approximation.

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.

An algorithm runs in polynomial time if its worst-case running time is bounded by a fixed polynomial in the input length. Arithmetic with fixed-degree algebraic numbers also needs polynomial bit cost when used in such a guarantee. The Edmonds–Karp algorithm and the method of conditional probabilities with efficiently computable clause expectations are examples.