Motivation
A CNF formula may be unsatisfiable, but we can still seek an assignment satisfying as much of it as possible. In weighted MAX-SAT, each clause has a nonnegative weight and the goal is to maximize the total satisfied weight. A random assignment gives a simple baseline: every nonempty clause is satisfied with probability at least one half.
The expectation argument also leads to a deterministic algorithm. Fix variables one at a time, choosing a value that does not decrease the conditional expected final score. This is an example of the method of conditional expectation: a probabilistic existence proof becomes an explicit sequence of choices.
Definitions
Definition 6.7.1
(Weighted MAX-SAT instance and score)
The input is a finite list of clauses over Boolean variables, with nonnegative rational weights . A clause is a disjunction of literal occurrences. Its score is its weight if at least one literal is true and zero otherwise. The score of an assignment is the sum of its satisfied-clause weights, and is the maximum score over all assignments.
A clause containing both and is tautological and always satisfied. Repeated copies of the same literal do not change the clause's truth value; remove duplicates when counting distinct variables. An empty clause is always false. We assume for the main theorem that every non-tautological clause is nonempty; empty clauses can be removed because they contribute zero to every assignment.
Definition 6.7.2
(Uniform random assignment and total weight)
Choose every variable independently and uniformly from false and true. Let over all nonempty clauses, including tautologies. Under the main assumption this is an upper bound on .
Theorems
Theorem 6.7.3
(A one-half approximation)
For weighted MAX-SAT with nonnegative weights and no empty clauses, a uniform random assignment has expected score at least . A deterministic polynomial-time conditional-expectation algorithm achieves score at least .
Theorem 6.7.4
(The exact-three-literal improvement)
If every clause has exactly three literals on three distinct variables, and no clause is tautological, the same random assignment has expected score . Conditional expectation yields a deterministic assignment of score at least .
Proofs
Proof: expectation of the score
Proof
(Expected score of a uniform assignment)
A non-tautological clause involving distinct variables is false exactly when each of its literals is false. The required values of those distinct variables are independent, so the falsity probability is . Its satisfaction probability is . A tautological clause is satisfied with probability one.
Let be the indicator that clause is satisfied. Its expected weighted contribution is . By linearity of expectation,
The clause indicators need not be independent: different clauses may share variables. Linearity does not require independence between them. Nonnegative weights ensure that replacing each satisfaction probability by its lower bound preserves the inequality. Since no assignment can score more than , this is at least .
When each clause has exactly three distinct variables and is not tautological, its falsity probability is exactly . Every satisfaction probability is , so the expected total is exactly . The same upper bound gives the approximation guarantee. The value is an expectation; individual assignments can score less or more.
Proof X-ray
Independence is used within a clause
Two kinds of probabilistic reasoning are combined, and only one of them needs independence. Inside a single clause, independence of the fair bits of distinct variables gives falsity probability exactly : the falsifying assignment fixes each of the variables to one value, and the probabilities multiply. Repeated variables would break this, because the literals are then not independent; the clause is false with probability , not . Across clauses only linearity of expectation is used, and it holds for any dependence between the indicators, so shared variables cost nothing. Nonnegative weights matter in the last step: replacing each by the lower bound preserves the inequality only when every weight is nonnegative.
Derandomization by conditional expectation
Proof
(Conditional expectation never decreases)
Process variables in any fixed order. Suppose some variables have already been fixed. Compute the expected final score if the next variable is set to false and the remaining variables stay uniformly random; also compute it if that variable is set to true. The current conditional expectation is the average of these two numbers, because the next variable is still a fair independent bit. At least one choice has conditional expectation at least the current value. Fix the variable to such a choice, breaking ties arbitrarily, and repeat.
After all variables are fixed, there is no remaining randomness. The conditional expectation is the actual score of the constructed assignment. It is at least the initial expectation, proving both deterministic guarantees.
The two expectations can be computed from the clauses. A clause already satisfied contributes its full weight. A clause whose fixed literals are all false and which has unassigned distinct variables contributes if and zero if . A tautology contributes its full weight. These quantities are rational and can be summed exactly. With rational input weights represented in binary, straightforward common-denominator arithmetic and repeated clause scans use polynomially many bits and operations; the power-of-two factors require at most the number of variables in their exponents.
Worked examples
Worked example 6.7.5
(One clause)
For the unweighted clause , exactly one of the eight assignments makes all three literals false. The expected score of a uniform assignment is . The optimum is one, and any assignment with at least one true variable attains it.
Worked example 6.7.6
(A conditional choice)
For the two unweighted clauses and , the initial expected score is . Setting true gives expected score , while setting false gives . Conditional expectation chooses . It then chooses , giving final score two.
Worked example 6.7.7
(Opposite unit clauses)
For and , each of weight one, every assignment satisfies exactly one clause. The expected score is one and the optimum is one. The upper bound is not always attainable, so an approximation proof using can be conservative.
Worked example 6.7.8
(Repeated literals do not add randomness)
The clause is false whenever is false, with probability , not . After duplicates are removed it is a unit clause. It does not meet the exact-three-distinct-variables hypothesis of the statement.
Common mistakes
Counterexample mode
Expectation is not a per-run guarantee
For the single clause , a random assignment has expected score , but the assignment scores zero. The deterministic conditional-expectation procedure chooses a value with enough conditional expected score; a single uninspected random run need not meet the expectation.
Common mistake
(Counting literal occurrences instead of distinct variables)
The factor requires three distinct variables in every clause. Three literal occurrences are not enough when a variable is repeated. Tautological clauses are always satisfied and can be handled separately, but their satisfaction probability is one rather than exactly .
Common mistake
(Ignoring the sign of the weights)
Nonnegative weights matter. With a negative clause weight, increasing the chance of satisfying that clause can decrease the score, and need not be an upper bound on the optimum in the same way. The theorem does not cover negative weights.
Understanding the deterministic choices
A partial assignment partitions each non-tautological clause into three cases. If a fixed literal is true, the clause is already guaranteed to contribute. If every literal is fixed false, it can contribute nothing. Otherwise all fixed literals are false and the remaining distinct variables must all take their unique falsifying values for the clause to fail. This gives the conditional contribution used by the algorithm.
The conditional expectation does not estimate what a particular greedy assignment will eventually score by guessing the future. It averages over all completions of the remaining variables. The two branches for the next variable partition those completions into equally likely halves, so one branch has average at least the current average. Repeating this argument prevents the guaranteed value from decreasing.
Weights and clauses may be repeated. Their contributions are counted separately, exactly as specified by the input list. Shared variables create dependencies between clauses, but evaluating each conditional contribution and summing it remains valid by linearity of expectation.
When the bound is attained
Take three variables and include all eight clauses obtained by choosing independently whether each variable appears positively or negatively. Give each clause weight one. Every clause contains three distinct variables, and .
For any assignment, exactly one of the eight clauses is false: choose in each position the literal made false by that assignment. The other seven clauses are satisfied. Thus every assignment has score seven, the optimum is seven, and the random expected score is exactly . This example shows that the guarantee relative to total clause weight cannot generally be improved for uniform random assignments under the exact-three hypothesis. It does not show an approximation ratio of relative to the optimum, because here every assignment is optimal.
Concept lensCombinatorial
Counting falsifying assignments
The expectation is also a count. A non-tautological clause on distinct variables is false under exactly of the assignments to variables, so the average score over all assignments is . In the example above each of the eight clauses is false under exactly one assignment, and each assignment falsifies exactly one clause, so the counts balance.
The distinction between a guarantee in terms of and one in terms of is useful. The inequality converts the former into the latter, but it can lose information when the clauses cannot all be satisfied. A sharper approximation analysis may use a better upper bound on than the total weight.
A weighted conditional calculation
Consider clauses of weight two, of weight three and of weight one. Initially their expected contributions are , and , totaling . If is true, the first clause contributes two, the second contributes in expectation, and the third contributes , for total four. If is false, the first contributes zero, the second contributes three and the third contributes , for total . The mean of four and is indeed .
Choose . Then choosing satisfies the first two clauses for score five, while choosing satisfies the first and third for score three. The algorithm chooses true and outputs score five, exceeding its initial expectation. No independence between the second and third clause indicators was assumed in this calculation; their conditional expected contributions were simply added.
Exact arithmetic and input size
For a partial assignment, powers have denominators with at most one plus the number of unassigned variables in binary length. Each input weight is a rational number with a binary numerator and denominator. Multiplying the input denominators gives a common denominator whose bit length is at most the sum of their bit lengths. Including the largest required power of two adds at most the number of variables to that length.
Consequently the conditional sums and comparisons can be carried out with integers of polynomial bit length. A naive implementation may rescan every clause for both values of every variable; this is still polynomial in the explicit input size. More efficient incremental updates are possible, but are not needed to establish the existence of a polynomial-time derandomization.
Summary
A uniform assignment satisfies every nonempty clause with probability at least one half, and every exact three-distinct-variable clause with probability seven eighths. Conditional expectation fixes variables without decreasing the expected total, yielding deterministic approximation guarantees under the stated nonnegative-weight model.
Exercises
Quick check
(What is the falsity probability of a non-tautological clause containing four distinct variables under a uniform assignment?)
Solution · Answer
The unique assignment falsifying all four literals has probability , so satisfaction has probability .
Quick check
(For the clauses and with equal weight, what is the score of every assignment?)
Solution · Answer
Exactly one of the two clauses is satisfied, so the score is one when each weight is one. The optimum is one even though the total clause weight is two.
Quick check
(Why does the expectation proof not require different clauses to be independent?)
Solution · Answer
The score is a sum of clause indicators. Expectation distributes over a finite sum regardless of dependence; only the probability of each individual clause needs to be computed.
Quick check
(Why can the conditional-expectation algorithm always select a value that does not decrease the current expectation?)
Solution · Answer
The current expectation is the average of the conditional expectations in the false and true branches. At least one of two real numbers is at least their average, so choosing that branch does not decrease the value.