10 · Complexity

Second hearing of Part II. Chapter 09 asked what computation can do at all; this one asks what it can do before the universe runs out of patience — and whether that second question is merely practical or cuts as deep as any distinction philosophy has drawn.

Is "possible in principle but not in practice" a metaphysical category?

In May 1971, at the third ACM Symposium on Theory of Computing, Stephen Cook presented "The Complexity of Theorem-Proving Procedures," proving that Boolean satisfiability — given a formula, does some assignment of true/false to its variables make it true? — has a peculiar property: every problem whose proposed solutions can be checked quickly reduces to it. Two years later, cut off from Western journals, Leonid Levin proved the identical theorem in the Soviet Union without having seen Cook's paper — a second independent convergence on the same result, the same shape as Church and Turing thirty-five years earlier. Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems" then showed that twenty-one familiar hard problems — the travelling salesman, graph coloring, clique — are all satisfiability in disguise. Cook, Levin, and Karp had located a single fault line: P, the class of problems solvable quickly, against NP, the class whose solutions can be checked quickly once found. Whether P equals NP is the most consequential open question in mathematics, and almost every expert believes the answer is no.

Scott Aaronson's 2011 manifesto "Why Philosophers Should Care About Computational Complexity" argues that this is not a technicality philosophy can set aside as an engineering detail. Classical epistemic logic assumes an agent who believes all the logical consequences of what she believes — logical omniscience — and treats the assumption as an idealization, the way physics idealizes frictionless planes. Complexity theory shows it is not an idealization but an impossibility: for many ordinary beliefs, deriving every consequence would outlast the universe even granted every computer humanity could ever build. Aaronson extends the same lens to Hume's problem of induction, to Newcomb's problem, and to economic rationality — in each case, a puzzle that looked purely conceptual turns out to have a computational skeleton nobody had priced in.

The clearest case of that skeleton is what P vs NP says about creativity. Checking a completed Sudoku, or a proposed mathematical proof, takes a fixed, modest amount of work regardless of how the answer was found; searching the space of all possible arrangements or all possible proofs is — if P ≠ NP — exponentially harder in the worst case, no matter how cleverly the search is organized. A mathematician's flash of insight, the moment a proof strategy presents itself, may be doing something no systematic algorithm can replace: recognizing is cheap, finding is not, and the distance between them is precisely what complexity theory measures. Chess supplies an older, purer instance of the same gap. Ernst Zermelo proved in 1913 that chess is determined — one of "White forces a win," "Black forces a win," or "both force at worst a draw" is simply true, since the game tree is finite. Nobody knows which, because "finite" and "searchable" are different claims; the game tree is too large for exhaustive analysis by any device anyone expects to build. "Solved in principle" and "true" turn out to be much further apart than either word suggests.

Herbert Simon anticipated the gap from the other direction, decades before complexity theory could measure it. His Administrative Behavior (1947) and "A Behavioral Model of Rational Choice" (Quarterly Journal of Economics 69, 1955: 99–118) replaced the classical agent — who surveys every option and every consequence before choosing the best — with a satisficer, who stops at the first option clearing a "good enough" threshold. Simon meant this as psychology, a description of how managers and shoppers actually decide; complexity theory later gave it a floor that is not psychological at all. Any agent operating under a real time budget — human, corporation, or algorithm — is a bounded-rational agent as a matter of physical necessity, whether or not it wants to be.

The same fault line, treated as a resource rather than an obstacle, built modern cryptography. Whitfield Diffie and Martin Hellman's "New Directions in Cryptography" (IEEE Transactions on Information Theory 22, 1976: 644–654) proposed that a "trapdoor one-way function" — easy to compute forward, computationally infeasible to invert without a secret key — could let two strangers agree on a shared secret over an open channel, though the paper offered no working example. RSA supplied one soon after: multiplying two three-hundred-digit primes takes a processor milliseconds; factoring the product back into its primes is believed, by every known method, to take longer than the universe has existed. Every padlock icon in a browser rests not on a proof but on an unproven complexity conjecture — one-way functions are, quite literally, the applied physics of keeping a secret.

Complexity theory's strangest offspring reworks what a proof even is. Shafi Goldwasser, Silvio Micali, and Charles Rackoff's "The Knowledge Complexity of Interactive Proof-Systems" (17th ACM Symposium on Theory of Computing, Providence, 1985; full version, SIAM Journal on Computing 18, 1989: 186–208) showed that a prover can convince a verifier a statement is true — "these two graphs are isomorphic," "I know the password" — through an interactive back-and-forth whose transcript, read afterward by anyone who wasn't part of the exchange, proves nothing at all. The evidential force lives entirely in the live interrogation and its shrinking probability of letting a cheat through, not in a static object anyone can inspect later. That breaks with every proof from Euclid onward, where a proof is a fixed thing you hand someone and they check alone; here philosophy has grounds to object that computation has redefined "proof" to mean something merely statistical, and complexity theory's honest answer is that the older picture of certainty was never available at scale in the first place — chapter 12 finishes that argument.

Whether "possible in principle but not in practice" earns the name metaphysical depends on whether the boundary is fixed or merely historical. Worst-case complexity classes are mathematical facts, but real instances are not always worst cases: practical SAT solvers now settle satisfiability questions with millions of variables that theory calls intractable, because most real formulas are far from the adversarial examples the proofs are built on. The gap between "P ≠ NP" and "this particular problem, today, on this hardware, is out of reach" is where sociology and engineering quietly do the work that pure complexity theory cannot yet certify.

Connections

Chapter 09 established what computation can do at all; this chapter measures what it can do inside a clock. Chapter 03 asked whether machine testimony counts as knowledge; interactive proof is that question with a probability attached. Chapter 06 meets the same impossibility-result shape in algorithmic fairness. Chapter 11 takes up Kolmogorov complexity, the cousin of computational complexity that measures description length rather than running time.

Open questions

If P vs NP were resolved tomorrow, would it settle a metaphysical question or only a mathematical one? Does the gap between worst-case hardness and real-world tractability mean complexity classes describe the world, or only the adversaries mathematicians have chosen to imagine? And if bounded rationality is a physical necessity for any agent, what is left of the classical picture of a fully rational ideal observer that philosophy built its theories of knowledge and choice around?

Go deeper

• Scott Aaronson, Quantum Computing Since Democritus (Cambridge: Cambridge University Press, 2013).
• Stephen Cook, "The Complexity of Theorem-Proving Procedures," Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971): 151–158; Scott Aaronson, "Why Philosophers Should Care About Computational Complexity" (2011) — arxiv.org/abs/1108.1791.
• Stanford Encyclopedia of Philosophy, "Computational Complexity Theory" — plato.stanford.edu/entries/computational-complexity.