- Atlas
- Computer Science
- Complexity Theory
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
- Computational Complexity Theory 1965-Present
- Circuit Complexity 1970-Present
- NP-completeness 1971-Present
- Descriptive complexity theory 1974-Present
- Barriers to Lower Bounds 1975-Present
- Structural Complexity and the Polynomial Hierarchy 1976-Present
- Randomized Computation and Derandomization 1977-Present
- Algebraic Complexity Theory 1979-Present
- Complexity-Theoretic Cryptography 1984-Present
- Interactive Proofs and Probabilistically Checkable Proofs 1985-Present
- Quantum Complexity Theory 1985-Present
- Hardness of Approximation 1991-Present
- Fine-Grained Complexity 2001-Present
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
- Computational complexity theory (introduction, Defining complexity classes, Problems in NP not known to be in P or NP-complete, History), Wikipedia
- Complexity class, Wikipedia
- P versus NP problem (introduction, History), Wikipedia
- Approximation algorithm, Wikipedia
- Time hierarchy theorem, Wikipedia
- Cook–Levin theorem, Wikipedia
- Boolean satisfiability problem, Wikipedia
- NP-completeness, Wikipedia
- Descriptive complexity theory, Wikipedia
- Finite model theory (History), Wikipedia
- PCP theorem, Wikipedia
- 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.
- 1965-Present
Computational Complexity Theory
How much time and memory does a problem require?
- 1970-Present
- 1971-Present
- 1974-Present
Descriptive complexity theory
Which logic expresses which complexity class?
- 1975-Present
Barriers to Lower Bounds
Which proof techniques cannot settle open separations?
- 1976-Present
Structural Complexity and the Polynomial Hierarchy
How do classes stack with alternating quantifiers?
- 1977-Present
Randomized Computation and Derandomization
Does randomness add power to efficient computation?
- 1979-Present
Algebraic Complexity Theory
How many arithmetic operations compute a polynomial?
- 1984-Present
Complexity-Theoretic Cryptography
What hardness makes secure encryption possible?
- 1985-Present
Interactive Proofs and Probabilistically Checkable Proofs
How much proof can be checked with little reading?
- 1985-Present
Quantum Complexity Theory
What can quantum machines compute efficiently?
- 1991-Present
Hardness of Approximation
Which optimization problems resist good approximation?
- 2001-Present
Fine-Grained Complexity
What exact running times are optimal for problems?
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.
Hardness of Approximation grew out of Interactive Proofs and Probabilistically Checkable Proofs
The PCP theorem turned interactive proof and probabilistically checkable proof techniques into inapproximability results, showing that many optimization problems cannot be approximated unless P = NP.
Carried by Sanjeev Arora; Shmuel Safra; Carsten Lund.
Algebraic Complexity Theory influenced by Circuit Complexity
Valiant's algebraic complexity theory translated the Boolean circuit model and NP-completeness ideas into arithmetic circuits, defining algebraic analogues of P and NP.
Carried by Leslie Valiant.
Quantum Complexity Theory influenced by Circuit Complexity
Deutsch's quantum circuit model adapted the Boolean circuit model of complexity to quantum gates, defining BQP as the quantum analogue of bounded-error polynomial-time computation.
Carried by David Deutsch.
Descriptive complexity theory influenced by NP-completeness
Fagin's existential second-order characterization of NP took NP, the class made central by Cook and Karp, as the object to be captured in logic.
Carried by Ronald Fagin.
Barriers to Lower Bounds influenced by NP-completeness
Baker, Gill and Solovay's relativization barrier was aimed at the P versus NP question crystallized by Cook and Karp, showing that oracle arguments cannot settle it.
Carried by Theodore Baker; John Gill; Robert Solovay.
Structural Complexity and the Polynomial Hierarchy grew out of NP-completeness
Stockmeyer's polynomial hierarchy generalized NP by stacking alternating quantifiers, building directly on the NP-completeness framework.
Carried by Larry Stockmeyer; Albert Meyer.
Complexity-Theoretic Cryptography influenced by NP-completeness
Goldwasser and Micali's probabilistic encryption grounded security in the assumed hardness of problems such as factoring and discrete log, which sit within the NP-hardness landscape.
Carried by Shafi Goldwasser; Silvio Micali.
Hardness of Approximation influenced by NP-completeness
Hardness of approximation results are conditional on P ≠ NP and use NP-completeness reductions to show that approximation would imply fast SAT algorithms.
Carried by Sanjeev Arora; Shmuel Safra.
Fine-Grained Complexity influenced by NP-completeness
Fine-grained complexity builds on the NP-completeness tradition but assumes the Strong Exponential Time Hypothesis to derive exact-exponent lower bounds, starting from Impagliazzo and Paturi's work.
Carried by Russell Impagliazzo; Ramamohan Paturi.
Interactive Proofs and Probabilistically Checkable Proofs influenced by Randomized Computation and Derandomization
Interactive proofs introduced a probabilistic verifier, taking the randomized computation model of BPP and applying it to proof verification.
Carried by Shafi Goldwasser; Silvio Micali; Charles Rackoff.
Barriers to Lower Bounds influenced by Randomized Computation and Derandomization
Randomized algorithms raised the question of whether randomness adds power, and results on derandomization became part of the barrier landscape about which proof techniques can separate classes.
Carried by Michael Rabin; Russell Impagliazzo; Avi Wigderson.
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.
Computational Complexity Theory influenced Proof Complexity in Theory Of Computation
Computational complexity theory provided proof complexity with its resource-bounded framework and the NP versus coNP question that motivates the field. Cook and Reckhow defined proof complexity in complexity-theoretic terms.
Carried by Stephen Cook; Robert Reckhow.
Computational Complexity Theory led to Communication complexity in Streaming Algorithms
Communication complexity grew directly out of computational complexity theory, with Yao's 1979 paper framing two-party communication as a complexity measure and later work applying it to streaming lower bounds.
Carried by Andrew Yao.
Computational Complexity Theory led to Fixed-Parameter Tractability in Parameterized Algorithms
Fixed-parameter tractability was introduced as a refinement of computational complexity theory, replacing a single input-size measure with a two-dimensional parameterized measure. The founders of parameterized complexity framed it explicitly as a new branch of complexity theory.
Computational Complexity Theory led to Proof complexity in Proof Theory
Proof complexity is a branch of computational complexity theory, applying its notions of resource-bounded computation to proofs; the Cook-Reckhow programme defined proof systems as nondeterministic computation and asked for lower bounds in complexity terms.
Carried by Stephen A. Cook; Robert A. Reckhow.
NP-completeness influenced Polynomial-time approximation scheme in Approximation Algorithms
NP-completeness, established by Cook and Karp around 1971, is the reason approximation schemes exist: once exact polynomial-time solution is ruled out, one seeks a tunable approximation. The PTAS is defined and motivated entirely within the NP-completeness framework.
Carried by Stephen Cook; Richard M. Karp.
NP-completeness grew out of Computational Complexity Theory in Theory Of Computation
NP-completeness grew directly out of computational complexity theory: Cook's 1971 theorem defined NP and proved SAT complete for it, and Karp's 1972 reductions established the class of NP-complete problems within the complexity framework.
Carried by Stephen Cook; Richard Karp.
Descriptive complexity theory grew out of Finite model theory in Database Theory
Descriptive complexity arose directly from finite model theory when Fagin characterized NP as existential second-order logic over finite structures; the two fields share their core results.
Carried by Ronald Fagin.
Descriptive complexity theory grew out of Computational Complexity Theory in Theory Of Computation
Descriptive complexity theory grew out of computational complexity theory: Fagin's 1974 theorem equated NP with existential second-order logic, recasting complexity classes as definability classes.
Carried by Ronald Fagin.
Barriers to Lower Bounds grew out of Computational Complexity Theory in Theory Of Computation
Barriers to lower bounds are results within computational complexity theory: the relativisation barrier of Baker, Gill and Solovay (1975) and later natural-proofs and algebrisation barriers were proved as theorems about the limits of complexity-theoretic techniques.
Carried by Theodore Baker; John Gill; Robert Solovay.
Structural Complexity and the Polynomial Hierarchy grew out of Computational Complexity Theory in Theory Of Computation
Structural complexity and the polynomial hierarchy grew directly out of computational complexity theory: Stockmeyer and Meyer defined the polynomial hierarchy in 1976 as a refinement of NP and co-NP within the complexity framework.
Carried by Larry Stockmeyer; Albert Meyer.
Randomized Computation and Derandomization led to Derandomization and pseudorandomness in Randomized Algorithms
Derandomization and pseudorandomness grew directly out of the study of randomized computation, asking when random choices can be replaced by pseudorandom ones. The Nisan-Wigderson and Blum-Micali constructions formalized this as a branch of complexity theory.
Carried by Manuel Blum; Silvio Micali; Noam Nisan.
Randomized Computation and Derandomization influenced Interactive proofs and probabilistically checkable proofs in Randomized Algorithms
The class of languages with interactive proofs was defined relative to randomized polynomial time, and PCP characterizations are stated in terms of randomized verifiers, so randomized complexity theory supplied the core definitions.
Carried by Goldwasser, Micali and Rackoff (1985); Arora and Safra (1998).

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 TheoryRelated fields
Fields its ideas are linked to
- Theory Of Computation 11 links
- Randomized Algorithms 7 links
- Combinatorial Optimization 6 links
- Algorithms 5 links
- Quantum Computation 5 links
- Approximation Algorithms 4 links
- Parameterized Algorithms 3 links
- Cryptography 3 links
- Distributed Algorithms 2 links
- Graph Algorithms 2 links
- Parallel Algorithms 2 links
- Database Theory 2 links
More in Theory Of Computation
- Algorithmic Game Theory
- Automata
- Computability
- Computational Learning Theory
- Computational Logic
- Cryptography
- Proof Complexity
- Quantum Computation
- Theory Of Computation
See where Complexity Theory sits on the Map of Human Knowledge