The PCP Theorem at the Intuition Level

A proof you can check by reading three bits of it. That is not a metaphor, and it is not a joke — it is the actual content of the PCP theorem, one of the strangest and most consequential results in complexity theory. This essay unpacks what that means, why it is shocking, the exact statement, and the load-bearing idea in Dinur's 2007 proof.

The claim, in plain English

A normal proof is something you read line by line. To be convinced, you read every line. The PCP theorem says: for every problem in NP, there is a reformatted proof where you can be convinced — with high probability — by reading a constant number of bits from the proof, using only logarithmically many random bits to decide which bits to look at. "Constant" means constant: the size of the proof grows with the problem, but the number of bits you read does not. Three is enough.

You are allowed to be wrong sometimes. Here is the shape of the promise. If the statement is true, there exists a proof the verifier always accepts. If the statement is false, then for every candidate proof, the verifier rejects with probability at least one half. You can drive the failure probability down to $2^{-k}$ by running the verifier $k$ times independently.

The deep surprise is that this can be done at all. Classical proofs have the property that flipping one bit in the middle can quietly change "valid proof of true statement" into "valid proof of different true statement" with no visible damage. For PCP proofs, flipping bits almost anywhere causes detectable local inconsistency. The proof is globally redundant in a way that makes it locally auditable.

A 3-SAT warm-up, so you see what is being promised

Take the 3-SAT formula $$\varphi = (x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor x_4) \land (x_2 \lor \lnot x_3 \lor \lnot x_4).$$ A classical NP "proof" that $\varphi$ is satisfiable is an assignment, say $x_1 = 1, x_2 = 1, x_3 = 0, x_4 = 1$. To verify, you plug in and check all three clauses. You read everything.

Now imagine a PCP verifier. It receives a much longer string $\pi$ that encodes not just an assignment but many derived quantities — parity bits, products, values of low-degree polynomials. The verifier tosses $O(\log n)$ random coins, computes three addresses into $\pi$, reads those three bits, and outputs accept or reject based on a local test. If $\varphi$ is satisfiable, some $\pi$ makes the verifier always accept. If $\varphi$ is unsatisfiable, every $\pi$ — honest or dishonest — makes the verifier reject at least half the time. That is the promise, and it is what the theorem delivers.

The formal statement

Let me introduce the class $\mathrm{PCP}[r(n), q(n)]$. Here $n$ is the length of the input $x$; $r(n)$ is the number of random bits the verifier is allowed to use; $q(n)$ is the number of bits of the proof it is allowed to read. The verifier is polynomial-time, runs on input $x$ and coin flips $R$, and makes $q(n)$ non-adaptive queries to a proof oracle $\pi$. A language $L$ is in $\mathrm{PCP}[r,q]$ if there is such a verifier $V$ satisfying:

• Completeness. If $x \in L$, then there exists a proof $\pi$ such that $\Pr_R[V^\pi(x, R) = 1] = 1$.
• Soundness. If $x \notin L$, then for every proof $\pi$, $\Pr_R[V^\pi(x, R) = 1] \leq \tfrac{1}{2}$.

Read aloud: $x$ is in $L$ iff there is a proof the verifier is certain about, and if $x$ is not in $L$ then no proof fools the verifier more than half the time.

The PCP theorem (Arora–Safra 1998; Arora–Lund–Motwani–Sudan–Szegedy 1998; reproved by Dinur 2007): $$\mathrm{NP} = \mathrm{PCP}[O(\log n),\, O(1)].$$

In words: every language in NP has proofs verifiable using $O(\log n)$ random bits and $O(1)$ queries, and nothing outside NP can be verified this way. The inclusion $\mathrm{PCP}[O(\log n), O(1)] \subseteq \mathrm{NP}$ is easy — enumerate all $2^{O(\log n)} = \mathrm{poly}(n)$ coin strings and accept iff the verifier accepts on a majority. The hard direction is $\mathrm{NP} \subseteq \mathrm{PCP}[O(\log n), O(1)]$. That is the theorem.

The tight version is Håstad's 3-bit PCP (2001): for every $\varepsilon > 0$, every NP language has a verifier that reads exactly three bits, accepts true statements with probability $1 - \varepsilon$, and accepts false statements with probability at most $\tfrac{1}{2} + \varepsilon$. Three is optimal in a strong sense — two queries with constant soundness gap would collapse NP into P.

The equivalent form you actually use: gap problems

The PCP theorem has an equivalent combinatorial face that is easier to work with. Define $\mathrm{Gap\text{-}3SAT}_s$: given a 3-SAT formula $\varphi$ with $m$ clauses, decide whether $\varphi$ is satisfiable, or whether no assignment satisfies more than a fraction $s$ of the clauses. The promise is that one of these holds.

Equivalent statement of the PCP theorem. There is a constant $s < 1$ such that $\mathrm{Gap\text{-}3SAT}_s$ is NP-hard.

Unpacking: the fraction of clauses you can satisfy is a fractional satisfaction score in $[0, 1]$. Ordinary 3-SAT is NP-hard to decide perfectly. The PCP theorem says there is a constant threshold $s$ below 1 — think of $s = 7/8 + \varepsilon$, which Håstad proved optimal — such that even distinguishing "satisfiable" from "at most $s$-satisfiable" is NP-hard. Approximation to better than $s$ is as hard as exact solution.

This is why the PCP theorem matters outside complexity: it is the source of essentially all optimal inapproximability results. MAX-3SAT, MAX-CUT, set cover, vertex cover — all of their hardness thresholds are downstream of PCP.

The proof landscape

The original 1990s proof is algebraic. You encode an NP witness as an evaluation table of a low-degree polynomial over a finite field $\mathbb{F}$, and use the Reed–Muller low-degree test: a random-line test that catches a function far from any low-degree polynomial with constant probability. Completeness is easy; soundness is an exercise in algebraic geometry over $\mathbb{F}$ that takes, in expanded form, hundreds of pages.

The modern proof is Dinur's gap amplification (2007), which is purely combinatorial and roughly twenty pages. I will sketch its engine.

Dinur's route: gap amplification

Reformulate SAT as constraint graph satisfaction. A constraint graph $G = (V, E, \Sigma, \mathcal{C})$ has vertices $V$, edges $E$, an alphabet $\Sigma$, and a constraint $c_e \subseteq \Sigma \times \Sigma$ on each edge. An assignment is a map $\sigma: V \to \Sigma$. Define $$\mathrm{UNSAT}(G) = \min_{\sigma} \Pr_{e = (u,v) \in E}\big[(\sigma(u), \sigma(v)) \notin c_e\big].$$

Read aloud: $\mathrm{UNSAT}(G)$ is the smallest fraction of edges that any assignment must violate. It is zero iff $G$ is satisfiable, and positive otherwise. Proving the PCP theorem is equivalent to showing that it is NP-hard to distinguish $\mathrm{UNSAT}(G) = 0$ from $\mathrm{UNSAT}(G) \geq \alpha$ for some absolute constant $\alpha > 0$.

Dinur's main lemma. There exist constants $\alpha_0 > 0$ and $C$ such that for every constraint graph $G$ over an alphabet of size $O(1)$, one can produce in polynomial time a constraint graph $G'$ with:

• $|G'| \leq C \cdot |G|$ (size blows up by a constant factor),
• if $\mathrm{UNSAT}(G) = 0$ then $\mathrm{UNSAT}(G') = 0$ (completeness preserved),
• $\mathrm{UNSAT}(G') \geq \min\big(2 \cdot \mathrm{UNSAT}(G),\ \alpha_0\big)$ (gap doubles until it hits a constant).

Iterate this $O(\log n)$ times starting from an NP-hard graph with $\mathrm{UNSAT} \geq 1/\mathrm{poly}(n)$, and you end up with a constant-size blowup and constant UNSAT gap. That is the theorem.

The load-bearing step

The main lemma is achieved by composing three operations, but the one doing the conceptual work is the powering step. Replace $G$ by $G^t$, whose vertices are the same as $G$ but whose edges correspond to length-$t$ walks; a new constraint says "any assignment to the endpoints must be explainable by some consistent assignment along the walk." Over the new (exponentially larger) alphabet, the UNSAT value multiplies roughly by $t$ — up to saturation near some constant.

Why does this work? Because $G$ is first made into an expander (a graph with spectral gap bounded away from zero). In an expander, random walks mix rapidly, so a small violated set $S \subset E$ is hit by a random length-$t$ walk with probability at least $\Omega(t \cdot |S|/|E|)$ until $t \cdot |S|/|E|$ is constant. The specific inequality that makes this go is the Expander Mixing Lemma: for a $d$-regular graph $G$ with second-largest eigenvalue (in absolute value) $\lambda$, and any subsets $S, T \subseteq V$, $$\left| e(S, T) - \frac{d |S| |T|}{|V|} \right| \leq \lambda \sqrt{|S| |T|}.$$

Read aloud: the number of edges between $S$ and $T$ is close to the number you would expect in a random graph of the same density, with error controlled by the spectral gap $d - \lambda$. Applied to walks, this forces a violated fraction $\varepsilon$ to grow under powering instead of averaging out.

The alphabet blows up to $|\Sigma|^{d^t}$, which is fine for constant $t$ but unusable for iteration. So the third step, composition, re-encodes every constraint using an inner PCP on a small alphabet, paying a constant factor in size and losing a constant factor in soundness. The numbers balance. That is the entire game.

The proof that powering multiplies the gap is where Dinur uses the most delicate counting; it is a careful argument about random walks on expanders, not a mystery, and it is proved rigorously. Completeness preservation is essentially syntactic. The expander construction is by explicit zig-zag or by taking tensor powers of a constant-size expander, both proven constructions.

What is tight, what is open, what I am hiding

Tight. Håstad proved that $s = 7/8$ is the optimal soundness for MAX-3SAT: approximating better than $7/8$ is NP-hard, and a trivial random assignment achieves $7/8$. Three queries is optimal, as noted.

Proved, sketched above. The PCP theorem itself; Dinur's gap amplification; the Expander Mixing Lemma (standard spectral proof).

Asserted, not proved here. That the composition step can be realized with a small-alphabet inner PCP at constant cost; that expanders of any desired size can be constructed in polynomial time; that the original 1990s algebraic proof works. All are established, none shown.

Open. The Unique Games Conjecture of Khot (2002) posits that a particular two-query PCP — where each constraint is a bijection — remains hard even with near-perfect completeness and tiny soundness. It would imply optimal inapproximability for MAX-CUT, vertex cover, and many others. It is neither proved nor refuted; the 2018 proof of the 2-to-2 Games Conjecture by Khot, Minzer, and Safra brought it much closer but did not close the case.

The shape of the story: a proof so redundant that three bits suffice, built from expander walks and algebraic encoding, revealing that approximation is the same problem as exact computation in disguise. You now know the theorem, the statement, the one step doing the work, and the boundary of what we know.