the Cook-Levin theorem
/ Cook-Levin = kuk-LAY-vin /
Every chain needs a first link. To prove a problem NP-hard we reduce a known-hard problem to it — but how did the VERY FIRST problem get crowned hard, with nothing to reduce from? The Cook-Levin theorem is that founding act: it proves, from scratch, that boolean satisfiability (SAT) is NP-complete. It is the cornerstone that makes the whole edifice of NP-completeness possible; once SAT is hard, everything else can inherit hardness from it by reduction.
The statement is: SAT is in NP, AND every problem in NP reduces to SAT in polynomial time. The first half is easy (a satisfying assignment is a short certificate). The second half is the deep part, and the proof idea is genuinely clever: take ANY problem A in NP. By definition A has a polynomial-time verifier V — really a nondeterministic machine that, on input x and a guessed certificate, runs for at most p(|x|) steps. Cook and Levin show how to write down, mechanically, a boolean formula F(x) that is satisfiable EXACTLY when that machine has an accepting computation on x. The formula's variables describe the entire computation: the contents of each tape cell at each time step, the machine's state at each step, the head position. Clauses then enforce the 'rules of physics' of the machine: the start configuration encodes x; each step follows the machine's transition rules; tape cells not under the head do not change; and the final state is accepting. A satisfying assignment to F(x) is therefore nothing but a valid accepting run of the machine — i.e. a proof that x is a yes-instance. So x is a yes-instance of A iff F(x) is satisfiable, and F(x) has only polynomially many variables and clauses, computable in polynomial time. That is the reduction A <=p SAT, for EVERY A in NP at once.
Why it matters so much: this one theorem converts the abstract definition of NP (anything with a polynomial verifier) into a single concrete problem, SAT, that is provably as hard as the whole class. After it, proving new problems NP-complete no longer requires reasoning about all of NP — you just reduce SAT (or its child 3-SAT) to your problem. The history is a nice footnote: Stephen Cook proved it in 1971; Leonid Levin proved an equivalent result independently in the USSR, hence the joint name. One honest note: the formula F(x) is constructed FROM the verifier's description, so the proof works because 'has a polynomial verifier' is itself a precise, mechanisable statement — the theorem is really about encoding a computation as logic.
Sketch the encoding for a tiny machine: introduce a variable T[i, t, s] meaning 'tape cell i holds symbol s at time t', and Q[q, t] meaning 'the machine is in state q at time t'. Clauses say: at t = 0 the tape spells out x; each cell either stays the same or changes exactly as a transition rule allows; exactly one state per step; and at the final step the state is 'accept'. The formula is satisfiable iff a valid accepting run exists.
F(x) encodes a whole computation as logic; a satisfying assignment IS an accepting run.
Cook-Levin is what bootstraps the NP-complete zoo: it is the only hardness result proved without reducing from a prior hard problem. Every later 'X is NP-hard' proof stands on this first link, reducing SAT (or 3-SAT) to X rather than re-running the tableau argument.