Ask a machine to solve a Sudoku from scratch and it may grind through the whole tree of possibilities, backtracking, undoing, trying again — an amount of work that grows explosively with the size of the grid. Ask it instead to check somebody else's completed Sudoku for correctness, and it can do that in a glance: read each row, each column, each box, confirm no repeats. Checking is fast. Finding is maybe not. The question of whether "fast to check" and "fast to find" are secretly the same size of problem is the P versus NP question, and it has resisted proof in either direction since it was first written down cleanly in the early 1970s.
P is the class of problems a computer can solve in a number of steps that grows only polynomially with the input's size — doubling the input at most multiplies the work by some fixed power, never by an exponential blowup. NP is the class of problems whose proposed solutions can be verified that fast, whether or not anyone has a fast way to find one. Every problem in P is trivially in NP — if you can solve it quickly you can certainly check a solution quickly. The open question is the reverse: is every problem whose answer is easy to check also easy to find? Most people who have stared at this problem long enough suspect not — that P is a strictly smaller class than NP — but "suspect" is not "prove," and the $1,000,000 Clay Millennium Prize for a proof either way remains uncollected.
The Cook-Levin theorem, proved independently by Stephen Cook and Leonid Levin in 1971, is the hinge the whole field turns on. It shows that Boolean satisfiability — given a formula built from ANDs, ORs, and NOTs over true/false variables, does some assignment of values make the whole thing true? — is NP-complete: every other problem in NP can be translated into an instance of SAT without blowing up the size of the problem more than polynomially. This means SAT is, in a precise sense, the hardest problem in NP: if anyone ever finds a fast algorithm for SAT, that algorithm can be repurposed to solve every problem in NP fast, collapsing P and NP into the same class at a stroke. Thousands of other problems — the traveling salesman's shortest route, graph coloring, protein folding's simplest models, bin-packing a [elsewhere] — have since been shown NP-complete too, all of them secretly SAT wearing a different coat, all of them rising or falling together.
The PCP theorem, proved in the early 1990s, says something stranger still: any mathematical proof, no matter how long, can be rewritten into a form where a skeptical reader need only glance at a small constant number of randomly chosen bits — not read the whole thing — to be convinced, with high probability, that the proof is either entirely valid or badly wrong somewhere. It sounds like it should be impossible: how can spot-checking a handful of bits out of a million-line proof catch a single subtle error buried on line 600,000? The theorem's answer is that the rewriting itself is the trick — it spreads any single error out so thoroughly across the whole encoded proof that a random spot-check has a real chance of landing on evidence of it, the way stirring a drop of dye through a glass of water means any small sample you draw will show color even though the dye itself was never near most of the glass. PCP is the theoretical seed behind an entire practical industry of probabilistically checkable proofs, zero-knowledge protocols, and the compressed verification schemes now used to make blockchains checkable without re-running every transaction.
What all three ideas share is a refusal to let "true" and "known to be true cheaply" be the same word. A Sudoku solution is true the instant it is filled in correctly, whether or not anyone ever checks it — but knowing it is true, for a machine with no oracle and no shortcuts, might cost work with no known upper bound. The proof checks itself in a glance only because someone did the expensive, invisible work of arranging it that way first.
Seed: Computational Complexity Theory — P vs NP, the Cook-Levin theorem, the PCP theorem.