Complexity Theory

Complexity theory is the branch of the theory of computation that asks not whether a problem can be solved by a machine, but how much of a resource — time, memory, randomness, communication, proof length — solving it requires.

13 frameworks, from 1965 to today · Theory Of Computation · Computer Science

still a working view ended · each leads to its entry below

Overview

Complexity theory is the branch of the theory of computation that asks not whether a problem can be solved by a machine, but how much of a resource — time, memory, randomness, communication, proof length — solving it requires1. Its central object is the complexity class: a set of problems solvable within a stated budget on a stated kind of machine12. The field's most famous open question, whether P equals NP, asks whether every problem whose solution can be checked quickly can also be solved quickly32. What is at stake is practical as well as mathematical: the hardness of certain problems is what makes cryptography possible, and the impossibility of solving others efficiently is what forces engineers to settle for approximation14.

Computability's Shadow and the Birth of Complexity (1930s–1960s)

The field grew out of computability theory. In the 1930s Alan Turing, Alonzo Church, Kurt Gödel and others gave precise models of mechanical procedure and showed that some problems admit no algorithm at all. But once the existence of algorithms was settled, a natural second question appeared: among the problems that can be solved, which can be solved feasibly? Early formal work on this came from the Soviet school1. Andrey Kolmogorov and his student Boris Trakhtenbrot studied resource-bounded computation in the 1950s, and in 1956 Trakhtenbrot and, independently, the American John Myhill gave early definitions of complexity classes. The decisive move came in 1965, when Juris Hartmanis and Richard Stearns published "On the Computational Complexity of Algorithms," defining time- and space-bounded complexity classes and proving the hierarchy theorems: giving a machine more time or memory strictly enlarges the class of problems it can solve15. This was the moment complexity became a discipline with its own theorems rather than a loose collection of observations.

NP-Completeness and the Shape of Hardness (1971–1973)

The idea that a problem could be hard in a structural sense crystallized in 1971, when Stephen Cook proved that the Boolean satisfiability problem (SAT) — deciding whether a formula of ANDs, ORs and NOTs can be made true by some assignment of its variables — is complete for NP, the class of problems whose proposed solutions can be checked in polynomial time637. "Complete" means every problem in NP can be efficiently translated (reduced) into SAT, so a fast algorithm for SAT would give fast algorithms for all of NP68. Leonid Levin reached the same conclusion independently in the Soviet Union around 197113. In 1972 Richard Karp showed that a whole catalogue of natural problems — travelling salesman, graph colouring, clique, set cover — are equally hard, and in 1973 Richard Karp and Richard Lipton, and separately Theodore Baker, John Gill and Robert Solovay, developed the theory of reductions that made "NP-complete" a precise and portable label. The practical consequence was enormous: thousands of optimization problems were shown to be equivalent in difficulty, and the field's central conjecture, P ≠ NP, became the organizing question of theoretical computer science.

Classes, Hierarchies and the Architecture of Complexity (1970s–1980s)

With NP in place, practitioners built an elaborate taxonomy. Space complexity classes such as L (logarithmic space) and PSPACE (polynomial space) were studied alongside time classes; the polynomial hierarchy, introduced by Larry Stockmeyer in 1976 and developed with Albert Meyer, stacked alternating quantifiers over NP to capture problems of increasing logical depth. The circuit complexity tradition, which measures the size and depth of Boolean circuits rather than machine steps, gave an alternative and often sharper lens: a problem is in P if it has polynomial-size circuits, and proving lower bounds on circuit size became a route toward separating classes. In 1982 Richard Feynman's observation that classical computers seem unable to simulate quantum systems efficiently led to the quantum circuit model, and in 1985 David Deutsch defined the class BQP, the problems solvable in polynomial time on a quantum machine. Meanwhile the descriptive complexity programme, launched by Ronald Fagin in 1974, characterized complexity classes by the logic needed to express them — Fagin showed NP is exactly the class of properties expressible in existential second-order logic — tying machine resources to logical syntax910.

Randomness, Interaction and Proof (1980s–1990s)

A second wave of ideas reshaped what a "computation" could be. In 1977 Robert Solovay and Volker Strassen, and independently Michael Rabin in 1980, gave randomized algorithms for primality testing, showing that flipping coins could make algorithms simpler and faster. This raised the question of whether randomness is genuinely powerful; the class BPP (bounded-error probabilistic polynomial time) was studied intensively, and a long line of work on derandomization — culminating in the 1990s and 2000s with results by Russell Impagliazzo, Noam Nisan, Avi Wigderson and others — showed that under plausible hardness assumptions, randomness can be eliminated. The same period produced the most surprising structural results in the field. In 1985 Shafi Goldwasser, Silvio Micali and Charles Rackoff introduced interactive proofs, where a probabilistic verifier questions a powerful prover; in 1988 László Babai, Lance Fortnow and Carsten Lund showed that interactive proofs could recognize far more than NP. In 1990 Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan proved that every problem in PSPACE has an interactive proof, and in 1992 the PCP theorem (Arora–Safra; Arora–Lund–Motwani–Sudan) showed that proofs can be checked by reading only a constant number of randomly chosen bits. The PCP theorem had a striking consequence for hardness of approximation: many optimization problems cannot be approximated well unless $P = NP$, because a good approximation algorithm would yield a fast SAT algorithm1112. This line of work also fed complexity-theoretic cryptography, where Goldwasser and Micali's 1984 work on probabilistic encryption and the 1985 Goldwasser–Micali–Rackoff results grounded security in computational hardness rather than information-theoretic secrecy.

Algebraic and Fine-Grained Turns (1990s–Present)

Algebraic complexity developed in parallel, asking how many arithmetic operations are needed to compute a polynomial or matrix product; the study of arithmetic circuits, initiated by work such as Leslie Valiant's 1979 algebraic analogues of NP-completeness, produced its own lower-bound programme and connections to the permanent and determinant. In the 2000s and 2010s, fine-grained complexity shifted attention from polynomial-versus-exponential to the exact exponents: assuming the Strong Exponential Time Hypothesis (introduced by Impagliazzo and Paturi in 2001), researchers derived tight conditional lower bounds for problems such as edit distance and orthogonal vectors, explaining why decades of algorithm design had failed to beat certain running times.

Barriers and the Present

The field has repeatedly collided with barriers to lower bounds. In 1975 Baker, Gill and Solovay showed that relativizing proof techniques cannot resolve P versus NP; in 1994 Alexander Razborov and Steven Rudich defined "natural proofs" and showed that a broad class of circuit lower-bound arguments cannot prove strong hardness without breaking cryptography. These results did not close the question but told practitioners which tools could not work. Today the main approaches — circuit lower bounds, proof complexity, algebraic methods, and the study of interactive and quantum models — descend directly from these episodes. Quantum complexity has grown into a field of its own, with results such as Shor's 1994 factoring algorithm and the 2018 demonstration that quantum computers can verify proofs for problems beyond NP (MIP* = RE). The central questions remain open: whether P equals NP, whether BQP strictly contains BPP, and whether any of the known barriers can be circumvented.

References

  1. Computational complexity theory (introduction, Defining complexity classes, Problems in NP not known to be in P or NP-complete, History), Wikipedia
  2. Complexity class, Wikipedia
  3. P versus NP problem (introduction, History), Wikipedia
  4. Approximation algorithm, Wikipedia
  5. Time hierarchy theorem, Wikipedia
  6. Cook–Levin theorem, Wikipedia
  7. Boolean satisfiability problem, Wikipedia
  8. NP-completeness, Wikipedia
  9. Descriptive complexity theory, Wikipedia
  10. Finite model theory (History), Wikipedia
  11. PCP theorem, Wikipedia
  12. Hardness of approximation (History), Wikipedia

The frameworks of Complexity Theory

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1965-Present

    Computational Complexity Theory

    How much time and memory does a problem require?

    Fly to its tower in Nousfarer

  2. 1970-Present

    Circuit Complexity

    How small can a circuit compute a function?

    Fly to its tower in Nousfarer

  3. 1971-Present

    NP-completeness

    Which problems are as hard as satisfiability?

    Fly to its tower in Nousfarer

  4. 1974-Present

    Descriptive complexity theory

    Which logic expresses which complexity class?

    Fly to its tower in Nousfarer

  5. 1975-Present

    Barriers to Lower Bounds

    Which proof techniques cannot settle open separations?

    Fly to its tower in Nousfarer

  6. 1976-Present
  7. 1977-Present

    Randomized Computation and Derandomization

    Does randomness add power to efficient computation?

    Fly to its tower in Nousfarer

  8. 1979-Present

    Algebraic Complexity Theory

    How many arithmetic operations compute a polynomial?

    Fly to its tower in Nousfarer

  9. 1984-Present

    Complexity-Theoretic Cryptography

    What hardness makes secure encryption possible?

    Fly to its tower in Nousfarer

  10. 1985-Present
  11. 1985-Present

    Quantum Complexity Theory

    What can quantum machines compute efficiently?

    Fly to its tower in Nousfarer

  12. 1991-Present

    Hardness of Approximation

    Which optimization problems resist good approximation?

    Fly to its tower in Nousfarer

  13. 2001-Present

    Fine-Grained Complexity

    What exact running times are optimal for problems?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Computational Complexity TheoryCircuit ComplexityNP-completenessDescriptive complexity theoryBarriers to Lower BoundsStructural Complexity and the Polynom…Randomized Computation and Derandomiz…Algebraic Complexity TheoryComplexity-Theoretic CryptographyInteractive Proofs and Probabilistica…Quantum Complexity TheoryHardness of ApproximationFine-Grained Complexity

Beyond the field

Where Complexity Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 70 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Complexity Theory is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Complexity Theory

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Complexity Theory sits on the Map of Human Knowledge