History of Computational Complexity Theory

Previously, we built a Turing machine and drew a line between the computable and the uncomputable. The halting problem sits on the far side of that line: no algorithm can solve it, period. But most problems we care about day to day, sorting a list, finding a shortest path, checking whether a number is prime, are computable. The question is how long it takes. And that question, not "can a machine solve this?" but "can a machine solve this before the heat death of the universe?", is the subject of computational complexity theory.

A letter nobody read#

The first person to ask the question clearly was Kurt Gödel, in a letter that almost nobody read for decades.

In 1956, Gödel wrote to John von Neumann, who was dying of cancer. The letter is mostly about logic, but buried in it is this: given a formula and a number $n$, decide whether the formula has a proof of at most $n$ symbols. Can that be done in about $n$ or $n^2$ steps, rather than by exhaustive search? Or does every procedure require exponentially many steps, on the order of $2^n$?

Gödel saw what was at stake. If the answer were polynomial, if proofs could be found as quickly as they could be checked, the consequences would be of the "greatest importance": mathematicians could be replaced by machines. Not in principle, exhaustive search over bounded-length proofs already does that, but in practice.

Von Neumann never replied. He died the following year, and the letter sat in an archive until it was rediscovered in the 1980s.

Counting steps#

To make the question precise, you need to measure how hard a problem is, not on a specific instance but in general, as a function of input size.

Take the palindrome checker from the previous video. On an input of length $n$, the head sweeps back and forth, comparing one pair of symbols per round trip. Each round trip traverses roughly $n$ cells, and there are roughly $n$ rounds, so the machine uses on the order of $n^2$ steps. We write this $O\left(n^2\right)$ and call it the time complexity of the algorithm.

In 1965, Juris Hartmanis and Richard Stearns published the paper that founded the field, formalizing what it means for a problem to require a certain amount of time and proving the first major theorem, the time hierarchy theorem: give a Turing machine strictly more time and it can solve strictly more problems. This sounds obvious. It is not. Proving it requires a careful diagonalization argument, the same self-referential trick Turing used for the halting problem, applied now to efficiency rather than computability.

P#

With time complexity in hand, you can start drawing lines. The most important one: a problem is in P if some Turing machine solves it in a number of steps bounded by a polynomial in the input length. Linear, quadratic, $n^{10}$: all polynomial. The exponent does not matter for this classification.

This might seem like a coarse distinction, and it is. But it captures something real. Polynomial-time algorithms tend to be practical; they scale. Exponential-time algorithms are intractable in a very concrete sense: $2^n$ steps on an input of length 100 will not finish during the lifetime of any computer you can build. Sorting is in P. Shortest paths are in P. Primality testing is in P, though that last one took until 2002 to prove.

NP, and the gap between finding and checking#

Here is where the subject gets its teeth. There are problems where finding a solution seems hard, but checking one is easy.

Take a Boolean formula built from variables, AND, OR, and NOT. The satisfiability problem asks: is there an assignment of true and false to the variables that makes the whole formula true? Handed an assignment, you check it by just evaluating the formula, in polynomial time. But finding a satisfying assignment, if one exists, seems to require trying an exponential number of possibilities.

A problem is in NP if a correct solution can be verified in polynomial time. P versus NP asks whether the gap between finding and checking is real, or whether every efficiently checkable problem has an efficient solver we have not found yet.

Pause and try: show that every problem in P is in NP.

Membership in NP asks for a polynomial-time verifier. If the problem is in P, you already have a polynomial-time solver. Use it as the verifier: ignore the proposed solution entirely, solve the instance from scratch, and answer accordingly. If you can solve it fast, you can certainly verify a solution fast: P sits inside NP, and the open question is only the other direction.

Cook, Levin, and the hardest problems in NP#

In 1971, Stephen Cook proved something that reframed the entire question: the satisfiability problem is NP-complete. Every problem in NP can be efficiently translated into an instance of SAT. A polynomial-time algorithm for SAT would therefore give a polynomial-time algorithm for every single problem in NP. Scheduling, graph coloring, protein folding, cryptanalysis: all of them. SAT is a universal target.

Leonid Levin arrived at the same insight independently in the Soviet Union, in isolation from the Western research community; his 1973 paper framed the problem in terms of search rather than decision, but the essential discovery was the same.

A year after Cook's paper, Richard Karp proved twenty-one problems from combinatorics, graph theory, logic, and number theory NP-complete: Hamiltonian cycles, graph coloring, integer programming, subset sum. Thousands of problems from every corner of mathematics and engineering have since joined the list. They are all, in a precise technical sense, the same problem. Solve any one efficiently and you solve all of them. Nobody has.

The barriers#

Almost every complexity theorist believes P and NP are different; if they were equal, every checkable proof could be found efficiently, and most of modern cryptography would break along the way. But believing and proving are different activities. People tried to prove $P\ne NP$. They failed. Then, more unusually, they proved theorems explaining why their techniques had to fail.

In 1975, Baker, Gill, and Solovay showed that relativizing techniques cannot resolve P versus NP. A proof relativizes if it still works when both solver and verifier get an arbitrary oracle, a black box answering some fixed set of queries for free. They constructed one oracle under which P equals NP and another under which it does not. So any proof that treats the machine as a black box can never settle the question.

In 1994, Alexander Razborov and Steven Rudich identified a second barrier, natural proofs. Most known circuit lower bounds work by finding a property that easy circuits cannot have but hard functions do. If sufficiently strong one-way functions exist, a standard cryptographic assumption, then no proof with this structure can establish bounds strong enough to separate P from NP. The very hardness assumptions we believe in prevent the most natural proof strategies from working.

The barriers do not mean the problem is unsolvable. They mean a successful proof must be unnatural and non-relativizing: it has to crack open the machine and reason about the computation itself.

A faster algorithm is a lower bound#

In 2010, Ryan Williams found something on that narrow path. He proved that NEXP, the class of problems solvable in exponential time by a nondeterministic machine, cannot be computed by ACC circuits: constant depth, polynomial size, built from AND, OR, and modular counting gates. A restricted model, not the full generality P versus NP needs. But the technique was new, and it cleared both barriers.

Williams showed that proving circuit lower bounds and designing faster algorithms are the same activity viewed from two directions. Solve circuit satisfiability faster than brute force by any superpolynomial factor, and you have proved that the class you are working with cannot be computed by circuits of that type. A faster algorithm implies a lower bound. Usually the two goals feel opposite. In certain settings they are locked together.

Seventy years on#

Gödel asked his question in 1956. Seventy years later, it is still open. The barriers tell us the standard techniques will not decide it, but the question has not stood still: the tools built to attack it, reductions, hierarchy theorems, circuit complexity, derandomization, have reshaped how we understand computation. And Williams's result suggests the path forward may be a deep entanglement between the algorithms we design and the limits we prove. The act of solving problems and the act of understanding their difficulty: those were never separate to begin with.

If you remember three things#

1. Gödel's 1956 letter asked whether proofs can be found as fast as they are checked; Hartmanis and Stearns made "how long" a mathematical question in 1965.
2. Cook, Levin, and Karp showed that thousands of problems are one problem: solve any NP-complete problem in polynomial time and all of NP collapses into P.
3. Relativization and natural proofs explain why the obvious attacks fail, and Williams's NEXP versus ACC result shows the remaining gap is passable: faster algorithms and lower bounds are two views of one object.