the PCP theorem
/ P-C-P /
Picture a 1000-page mathematical proof. To be sure it is correct you would normally read every line. The PCP theorem makes a claim that sounds impossible: there is a way to rewrite any proof so that you can be almost certain it is valid by reading only a tiny, randomly chosen handful of its symbols. Spot-check three pages, and if the proof is wrong you will catch the error with good probability; read a few more and your confidence becomes overwhelming.
Stated for complexity, PCP says: every problem in NP has a proof format and a verifier that uses only a constant number of random coin flips and reads only a constant number of bits of the proof, yet satisfies completeness (a true claim has a proof the verifier always accepts) and soundness (for a false claim, every alleged proof is rejected with probability at least 1/2). The trick is that the proof is encoded so robustly that any flaw is smeared across the whole document — there is no way to make a wrong proof that is locally consistent almost everywhere, so a few random probes are very likely to hit the spread-out evidence of the lie. Symbolically, NP = PCP(O(log n), O(1)): logarithmically many random bits, constantly many queries.
Beyond being a stunning fact about proofs, the PCP theorem is the engine of hardness of approximation. The robust encoding creates a 'gap': true instances are almost fully satisfiable while false ones cannot be satisfied beyond some fraction. An algorithm that approximated the optimum closely would distinguish these two and thereby solve the underlying NP-complete problem exactly — so good approximation would force P = NP. Almost every modern inapproximability result, from MAX-3SAT to graph coloring, descends from the PCP theorem. It is a deep, hard-won result (proved in the early 1990s, later given a combinatorial proof by Dinur).
Think of encoding a yes/no answer not as one bit but as a long error-correcting codeword spread over thousands of bits. If the prover writes the wrong answer, the encoding forces a huge fraction of the codeword to be 'off', so a verifier sampling just a few random positions almost surely lands on a wrong bit and rejects — no need to read the whole thing.
PCP rewrites a proof so any error is spread everywhere; a few random spot-checks catch a lie.
PCP does not let you check an arbitrary, ordinary proof by reading a few bits — the proof must first be re-encoded into the robust PCP format. And soundness is probabilistic: a single round catches a false proof with probability at least 1/2, and repetition amplifies that toward certainty.