A uniformly random assignment satisfies 7m/8 of the clauses of a 3-CNF formula, in expectation, because each clause on three distinct variables is satisfied by 7 of its 8 local assignments and expectations add. Since some value is at least the average, an assignment satisfying at least 7m/8 clauses must exist — a proof of existence that constructs nothing. The lab enumerates every assignment and shows which ones do worse.
Core ideas
The hard idea is that an average proves an existence. The other two are why the expectation needs no independence and why the ratio is against the optimum.
Take a clause on three distinct variables, say x₁ ∨ x₂ ∨ ¬x₃. Fixing the three variables gives 8 possibilities and exactly one falsifies the clause: the one that makes every literal false. So P(clause satisfied) = 7/8 when the assignment is uniformly random, whatever the signs are. The lab computes this per clause, from the clause's own variables, and prints it as a share.
Let Zⱼ be 1 if clause j is satisfied. The number satisfied is Σ Zⱼ, so E[Σ Zⱼ] = Σ E[Zⱼ] = 7m/8. The clauses overlap heavily — the lab's opening formula has four clauses on three variables, so every pair shares two of them — and the Zⱼ are strongly dependent. Linearity is indifferent, which is why this argument is two lines rather than an inclusion–exclusion.
A random variable cannot always be strictly below its own expectation, so some assignment satisfies at least 7m/8 clauses. That is a complete existence proof and it names no assignment: the lab has to enumerate all 2ⁿ of them to say which one. The gap between “one exists” and “here it is” is the whole difference between this argument and an algorithm.
The material
The 7m/8 bound, the linearity that gets it, the existence it proves, and the distribution it says nothing about.
A 3-CNF formula is a conjunction of m clauses, each a disjunction of three literals, where a literal is a variable or its negation. MAX-3-SAT asks for the assignment satisfying as many clauses as possible. The lab writes a clause as three signed integers, so 1 2 -3 is x₁ ∨ x₂ ∨ ¬x₃, and separates clauses with a semicolon.
Let F have m clauses, each on three distinct variables. Setting every variable to true or false independently with probability 1/2 satisfies 7m/8 clauses in expectation, exactly, whatever the clauses are and however much they overlap.
Fix a clause j. Its three literals involve three distinct variables, so the eight assignments to those three variables are equally likely under the random assignment. Exactly one of the eight makes all three literals false, namely the one setting each variable against its literal's sign. So P(Zⱼ = 1) = 7/8 and E[Zⱼ] = 7/8.
The number of satisfied clauses is Z = Σⱼ Zⱼ. By linearity of expectation, E[Z] = Σⱼ E[Zⱼ] = m·(7/8) = 7m/8, with no assumption about how the clauses share variables.
□
Every 3-CNF formula with m clauses, each on three distinct variables, has an assignment satisfying at least ⌈7m/8⌉ clauses.
`
Z
`
t
a
k
e
s
f
i
n
i
t
e
l
y
m
a
n
y
v
a
l
u
e
s
w
i
t
h
t
o
t
a
l
p
r
o
b
a
b
i
l
i
t
y
`
1
`
.
I
f
e
v
e
r
y
v
a
l
u
e
w
e
r
e
s
t
r
i
c
t
l
y
l
e
s
s
t
h
a
n
`
E
[
Z
]
`
,
t
h
e
n
`
E
[
Z
]
`
w
o
u
l
d
b
e
a
w
e
i
g
h
t
e
d
a
v
e
r
a
g
e
o
f
n
u
m
b
e
r
s
a
l
l
s
t
r
i
c
t
l
y
b
e
l
o
w
i
t
,
w
h
i
c
h
i
s
i
m
p
o
s
s
i
b
l
e
.
S
o
s
o
m
e
a
s
s
i
g
n
m
e
n
t
h
a
s
`
Z
≥
E
[
Z
]
=
7
m
/
8
`
,
a
n
d
s
i
n
c
e
`
Z
`
i
s
a
n
i
n
t
e
g
e
r
i
t
s
a
t
i
s
f
i
e
s
a
t
l
e
a
s
t
`
⌈
7
m
/
8
⌉
`
c
l
a
u
s
e
s
.
□
That is the probabilistic method in its simplest form: to show an object with a property exists, put a distribution on the objects and show the property holds on average. Nothing in it is constructive. The proof holds for a formula with a thousand variables, and finding the assignment it promises is a different problem, which Intractability and Approximation takes up.
x₁ ∨ x₂ ∨ ¬x₃, ¬x₁ ∨ x₂ ∨ x₃, x₁ ∨ ¬x₂ ∨ x₃, ¬x₁ ∨ ¬x₂ ∨ ¬x₃. Each clause has three distinct variables, so each contributes 7/8 and the mean is 4 × 7/8 = 7/2, which is what 7m/8 predicts. Enumerating all 8 assignments confirms it: four of them satisfy 3 clauses and four satisfy 4, and the mean of that is 7/2 exactly.
The clause table on the panel is the proof performed rather than quoted: each row computes that clause's own satisfying fraction over its own variables, and the last row adds the four shares and checks the total against the mean over all assignments. Two independent computations of the same number — one by linearity clause by clause, one by enumerating every assignment — and they agree.
It does not say a random assignment satisfies 7/2 clauses; no assignment satisfies half a clause. It does not say most assignments are at or above the mean: here exactly four of the eight are below it, a probability of 1/2. And it does not say the best assignment is anywhere near the mean. Those are three separate facts and the lab prints all three because the expectation on its own invites all three mistakes.
The measured column makes the first point concrete. Over 120 seeded coin flips the mean came out 139/40 = 3.475 against an expectation of 3.5, with every individual run landing on 3 or 4. The sample mean is close and it is not the expectation, and it is the average of integers each of which is not 3.5.
A randomised algorithm that outputs a uniformly random assignment is a 7/8-approximation for MAX-3-SAT, and the word 7/8 is a ratio to the optimum, not to m. On this formula the optimum is 4 and the mean is 7/2, so the ratio is 7/8 and the two coincide, because the formula is satisfiable. Change the formula and they part.
Take all eight clauses on three variables. The formula is unsatisfiable: every assignment falsifies exactly one clause, so every assignment satisfies exactly 7 and the optimum is 7, not 8. The mean is 7m/8 = 7 as well, so the ratio against the optimum is 1 while the ratio against m would be 7/8. The panel prints the optimum it found by enumeration beside the ratio, because a ratio printed without the thing it is a ratio to is not a ratio.
And take eight clauses on five variables: the mean is 7, the optimum is 8, and 9 of the 32 assignments do worse than the mean. That instance is the one to keep in mind, because it is the shape the guarantee is really about — a satisfiable formula where the average is genuinely below the best, and the gap is what an algorithm has to close.
Interactive
The mean over every assignment is a fraction, the best assignment is found by enumeration, and the ratio between them is what the algorithm earns
Method
Establish the average, then take one step, then stop — the step after that is a different problem.
One clause, its own variables, its own satisfying fraction. Do not try to reason about the formula as a whole; the point of linearity is that you never have to.
The clauses share variables and their indicators are dependent. Linearity applies anyway. If a step in your argument needs the clauses to be independent, it is not this argument.
Some value is at least the average. That gives an object and does not give a way to find it, and the sentence after it should not pretend otherwise.
7/8 is the mean over the best possible, and on an unsatisfiable formula the best possible is below m. The lab enumerates to find it. A ratio computed against m flatters the algorithm on exactly the instances where it matters.
x₁ ∨ x₂ ∨ ¬x₃, ¬x₁ ∨ x₂ ∨ x₃, x₁ ∨ ¬x₂ ∨ x₃, ¬x₁ ∨ ¬x₂ ∨ ¬x₃. Eight assignments, and the mean of the last column is the thing the theorem predicts.
Four assignments reach 4 and four reach 3. The existence claim asks for one reaching ⌈7/2⌉ = 4 and there are four of them, which is much more than the proof promised — the proof only ever promises one, and on a formula where the distribution is lopsided it may be promising exactly one.
The three routes to 7/2 are worth separating. The column of eight integers averaged is an enumeration over assignments. The sum of four 7/8 shares is linearity over clauses. 7m/8 is the closed form. They agree because the clauses all have three distinct variables, and the next lesson is what happens when one of them does not.
For a faded rehearsal, add the clause x₁ ∨ x₂ ∨ x₃ to the formula and predict the new mean before the panel redraws. The supplied first move is this: the new clause has three distinct variables, so it contributes 7/8 like the others, and m is now 5. Say what the mean becomes, then say whether the optimum is still 4 — and check both.
You should be able to compute a clause's satisfying fraction from its own variables, add the shares by linearity without invoking independence, take the one step to existence, and compute an approximation ratio against an optimum you have actually found.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.