the PCP theorem
/ P-C-P /
Imagine someone hands you a thousand-page proof of a hard claim and you must decide whether it is correct — but you are only allowed to read three random words of it. Surely you would miss errors. The PCP theorem (probabilistically checkable proofs) makes the astonishing assertion that this is essentially possible: every claim with a proof at all can be rewritten into a special robust format that a verifier can check by flipping a few coins and reading only a CONSTANT number of bits, catching any flawed proof with high probability.
Stated more carefully, it is a theorem about the class NP — the problems whose YES answers have short, polynomial-time-checkable certificates. The PCP theorem says NP = PCP(O(log n), O(1)): every NP problem has a proof system in which the verifier uses only O(log n) random bits and reads only O(1) (a constant number of) bits of the proof, yet (completeness) a correct proof of a true statement is always accepted, and (soundness) any 'proof' of a false statement is rejected with probability at least, say, 1/2. The magic is that ordinary proofs are brittle — change one symbol and correctness can hinge on exactly that spot — whereas a PCP-format proof is encoded so that ANY error contaminates a constant fraction of the proof, making it detectable by spot-checking a few random locations. Transforming a normal proof into this error-spread-out form is the deep technical heart of the theorem.
Why a proof-checking theorem belongs in a chapter on approximation: it is the engine of inapproximability. The connection (the 'PCP-to-gap' correspondence) is that a probabilistic verifier reading a constant number of bits can be encoded as a constraint-satisfaction instance, and the completeness-versus-soundness gap (accept always vs. reject half the time) becomes an unbridgeable gap between the optima of YES and NO instances. That manufactured gap is precisely what gap-producing reductions need, so the PCP theorem is what unlocked sharp hardness-of-approximation results — for MAX-3SAT, set cover, clique, and many more. Honesty about scope: the theorem is a profound and famously intricate result (its proof is one of the hardest in complexity theory); it characterizes worst-case difficulty under P != NP, and it explains WHY certain approximation barriers are real rather than merely unbeaten so far.
Via PCP, MAX-3SAT becomes a sharp gap problem: it is NP-hard to tell apart formulas where ALL clauses can be satisfied from those where at most 7/8 + epsilon of the clauses can. Any algorithm approximating better than 7/8 would cross that gap and decide an NP-hard problem — so 7/8 is the best possible approximation unless P = NP.
A constant-bit probabilistic verifier becomes a hardness gap — the bridge from PCP to inapproximability.
The PCP theorem does not give a faster way to FIND proofs — verification still needs the full proof to exist. Its power is that checking can be done by reading O(1) bits, which manufactures the YES/NO gaps that make sharp inapproximability results possible.