P versus NP

The letter sounded like a complaint. Kurt Gödel, writing to John von Neumann in 1956: if a proof is easy to check, why should finding one be a nightmare? The irritation was already old. Computers made it worse.

Picture a sudoku. Filling the grid from scratch is a scramble through dead ends. Checking a finished grid is a glance: scan each row, column, and block. That gap (hard to invent, easy to verify) kept showing up once computers were asked to schedule trucks, pack boxes, route wires on a chip, or satisfy a tangle of logical rules.

In the 1950s and 1960s, people who wrote algorithms noticed a split. Some jobs scaled politely: multiply two numbers, sort a list, find a shortest path in a friendly graph. Double the input size and the work grows by a manageable factor. Theorists later called that polynomial time: the running time is roughly a power of the input size, not an explosion. Other jobs seemed to demand a frantic search: try this arrangement, reject it, try the next. Each extra variable could roughly double the work.

Stephen Cook (1971) and, independently, Leonid Levin on the other side of the Iron Curtain, made the split precise. Two people. Two worlds. Same itch. Class P is the family of yes/no questions a computer can settle efficiently. Class NP is the family where every “yes” comes with a short witness you can check efficiently: a filled sudoku, a tour of cities, an assignment of true and false that obeys every clause. Cook showed that Boolean satisfiability (the puzzle of setting switches so every logical rule is true) is complete for class NP: if that puzzle has a fast algorithm, so does every problem in the class.

Richard Karp soon listed dozens of natural problems with the same status: routing, packing, clique-finding, and more. A private worry of algorithm designers became a public dare. Are finding and checking secretly the same power, or is there a real wall between them?

Decades of clever algorithms have shaved constants and conquered special cases. For the hardest problems in class NP, the best exact methods still look exponential in the worst case: fine for a dozen variables, hopeless for a few hundred. Industry lives with heuristics, approximations, and luck. Cryptography, in particular, bets that some answers stay hard to find even when they are easy to check.

Theory has partial trophies: lower bounds in restricted models, barriers that rule out certain proof styles, and a zoo of finer complexity classes. None settles whether the two classes are equal. The question is still open in the same blunt sense it was in 1971.