Loading field map
Complexity theory is the branch of theoretical computer science that studies the inherent difficulty of computational problems. Where computability theory asks which problems can be solved by algorithms at all, complexity theory asks how efficiently they can be solved, and how that efficiency scales as the inputs grow. Its central object of study is not any particular algorithm, but the intrinsic resource requirements—chiefly time and memory—that any correct algorithm for a given problem must consume.
The foundational move of complexity theory is to classify problems not by the exact number of steps an algorithm takes, but by how that number grows as a function of the input size. An algorithm that takes \(n^2\) steps on an input of size \(n\) is considered efficient in a way that one taking \(2^n\) steps is not, because the latter becomes unusable for even modest inputs. This leads to the distinction between polynomial time (roughly, feasible) and exponential time (roughly, infeasible), a coarse but remarkably robust boundary.
The field's central questions revolve around resource trade-offs. Given a problem, what is the minimum time or space required to solve it? Can a problem be solved faster if we allow more memory? Can a problem that is hard to solve be easy to verify—that is, can a proposed solution be checked quickly even if finding it is slow? The most famous of these questions, the P versus NP problem, asks whether every problem whose solutions can be verified quickly can also be solved quickly. This is not merely a technical curiosity: thousands of practical problems, from scheduling to protein folding to circuit design, are known to be NP-complete, meaning that if any one of them has a polynomial-time algorithm, then all of them do. The question of whether P equals NP is thus a question about the fundamental limits of efficient computation, and it remains one of the deepest open problems in mathematics.
Complexity theory emerged from the confluence of several mid-twentieth-century developments. In the 1930s, the formalization of computation by Alan Turing, Alonzo Church, and others established a precise notion of what an algorithm is. But the early theory of computability was not concerned with efficiency. The shift toward resource-bounded computation began in the 1960s, when researchers such as Juris Hartmanis and Richard Stearns introduced complexity classes—sets of problems solvable within a given resource bound—and proved the first hierarchy theorems showing that more time or space allows strictly more problems to be solved.
The field took its modern shape in the early 1970s with the independent work of Stephen Cook and Leonid Levin, who identified the class NP (problems verifiable in polynomial time) and showed that a specific problem—the satisfiability of Boolean formulas—was complete for it. This meant that every problem in NP could be reduced to it in polynomial time, so that a fast algorithm for satisfiability would yield fast algorithms for all of NP. Richard Karp then demonstrated that a large collection of natural combinatorial problems were also NP-complete, establishing the phenomenon as pervasive rather than isolated. This framework transformed the field: instead of studying individual problems in isolation, researchers could now study entire equivalence classes of problems under polynomial-time reducibility.
The modern field is organized around a rich hierarchy of complexity classes, each defined by a resource bound and a mode of computation. The most fundamental are:
These classes are known to form a chain of inclusions: P ⊆ NP ⊆ PSPACE ⊆ EXP. It is known that P is strictly contained in EXP, and that PSPACE is strictly contained in EXP, but the strictness of the inclusions between P, NP, and PSPACE is unknown. The central open problem is whether $P = NP$; the related question of whether $NP = PSPACE$ is also open.
Beyond these classical classes, the field has developed a rich taxonomy of more exotic classes. Randomized computation considers algorithms that can flip coins, leading to classes like RP (problems solvable in polynomial time with one-sided error) and BPP (problems solvable with bounded two-sided error). Interactive proofs allow a verifier to exchange messages with a prover, leading to the class IP, which was shown to equal PSPACE—a surprising result demonstrating that verification with interaction is far more powerful than static verification. Probabilistically checkable proofs (PCPs) refine this idea further, showing that proofs can be checked by reading only a constant number of randomly chosen bits, a result with deep implications for the hardness of approximation.
The earliest approach to complexity theory, inherited from computability theory, uses diagonalization—constructing a problem that differs from every problem in a given class by simulating all algorithms in that class and flipping the answer. This technique yields the hierarchy theorems, which show that more resources strictly increase the set of solvable problems. Its power is also its limitation: diagonalization is a "black-box" technique that treats algorithms as opaque machines, and it is known that such techniques cannot resolve the P versus NP question, because they would also apply to a hypothetical world where P equals NP. This limitation was formalized in the 1980s through the concept of relativization: diagonalization proofs remain valid when all algorithms are given access to the same oracle (a black-box subroutine), and since there exist oracles relative to which P equals NP and others relative to which they differ, no such proof can settle the question.
A second major approach studies computation through Boolean circuits—acyclic networks of logic gates that compute a function on a fixed input length. Circuit complexity asks how many gates are needed to compute a given function, and it has produced the strongest known lower bounds for explicit functions. The key insight is that circuits are a more rigid model than Turing machines: they have no loops or memory, so proving that a function requires many gates is a purely combinatorial task. However, the known lower bounds are still far from what would be needed to separate P from NP. A notable success of this approach is the proof that the parity function requires exponentially large circuits of constant depth, a result that separates small-depth circuit classes and has implications for the power of parallel computation. The main barrier here is the difficulty of proving lower bounds for unrestricted circuits, which remains one of the hardest problems in the field.
In the 1990s, Alexander Razborov and Steven Rudich identified a fundamental obstacle to circuit lower bounds, which they called natural proofs. They observed that all known lower-bound proofs share a common structure: they identify a statistical property of functions that is easy to test and that no function computable by small circuits possesses. They then showed that if such a property exists, it can be used to break pseudorandom generators—functions that produce outputs indistinguishable from random—which would have devastating consequences for cryptography. This means that proving strong circuit lower bounds would require techniques that are fundamentally different from all known ones, or else would imply the insecurity of most modern cryptography. This result reframed the field: it explained why progress on lower bounds had stalled and redirected attention toward understanding the connections between complexity theory and cryptography.
A third major research programme, which emerged in the early 1990s, concerns the approximability of optimization problems. Many NP-complete problems are optimization problems: finding the largest clique in a graph, the smallest vertex cover, or the shortest tour visiting a set of cities. The PCP theorem—the result about probabilistically checkable proofs mentioned above—has a striking consequence: for many NP-complete optimization problems, even finding a solution that is approximately optimal (within any constant factor) is as hard as solving the problem exactly. This result transformed the study of approximation algorithms, establishing a precise boundary between problems that admit good approximations and those that do not. It also revealed a deep connection between the power of proof verification and the difficulty of optimization, a connection that continues to drive research.
A distinct approach, sometimes called descriptive complexity, characterizes complexity classes not by the machines that solve problems but by the logical languages needed to express them. The foundational result here is that a problem is in P exactly when it can be expressed in first-order logic with a least-fixed-point operator, and in NP exactly when it can be expressed in existential second-order logic. This perspective recasts complexity-theoretic questions as questions about the expressive power of logical systems, and it has produced elegant characterizations of many classes. Its limitation is that it has not yet yielded new separations between classes, but it provides a powerful conceptual tool for understanding what makes problems hard.
A recurring theme in the field is the role of randomness in computation. Randomized algorithms—which make random choices during execution—are often simpler and faster than their deterministic counterparts. A central question is whether randomness actually helps: can every randomized polynomial-time algorithm be replaced by a deterministic one with only a polynomial slowdown? The current consensus, supported by a large body of evidence, is that randomness does not add power: under plausible assumptions about the existence of hard problems, every randomized algorithm can be derandomized. This belief is captured in the conjecture that $P = BPP$. However, the proof of this equivalence would require exactly the kind of circuit lower bounds that natural proofs suggest are difficult to obtain, creating a subtle circularity at the heart of the field.
Interaction, similarly, has been shown to be surprisingly powerful. The result that $IP = PSPACE$ means that a verifier who can exchange messages with an all-powerful prover can decide any problem solvable with polynomial memory, even though the verifier itself is limited to polynomial time. This result, proved in the early 1990s, was a major surprise and led to the development of zero-knowledge proofs, which allow a prover to convince a verifier of a statement's truth without revealing any information beyond the statement itself. Zero-knowledge proofs have become a cornerstone of modern cryptography, and they illustrate how complexity theory's abstract questions about resource bounds can have direct practical consequences.
The field today is characterized by a deep understanding of the relationships between many complexity classes, combined with a persistent inability to prove the separations that would resolve its central questions. The P versus NP problem remains open, as do the related questions of whether NP equals PSPACE and whether P equals BPP. What has changed is the sophistication of the tools brought to bear on these questions.
One active area is fine-grained complexity, which moves beyond the coarse polynomial/exponential distinction to ask about the exact exponent in the running time of algorithms. The strong exponential time hypothesis (SETH) posits that satisfiability requires essentially exponential time, and it has been used to prove tight lower bounds for a wide range of problems, showing that many known algorithms are optimal up to subpolynomial factors. This research programme has brought complexity theory closer to the practical concerns of algorithm design.
Another active area is the study of algebraic complexity, which considers circuits whose gates perform arithmetic operations over a field rather than Boolean operations. This model has its own version of the P versus NP question, known as the VP versus VNP problem, and it has proved more tractable than its Boolean counterpart: there are known lower bounds for algebraic circuits, and the field has developed deep connections to algebraic geometry and representation theory.
The relationship between complexity theory and cryptography has also deepened. Modern cryptography relies on the existence of one-way functions—functions that are easy to compute but hard to invert—and the security of cryptographic protocols is typically proved by reduction to such assumptions. This means that cryptography is, in a precise sense, the applied branch of complexity theory: it converts the field's conjectures about hardness into practical guarantees. The natural proofs barrier shows that this connection runs in both directions: strong lower bounds would imply the insecurity of many cryptographic constructions, so the two fields are locked in a delicate balance.
Finally, quantum computation has introduced a new dimension to the field. The class BQP—problems solvable efficiently by a quantum computer—is known to contain some problems believed to be outside P, most notably factoring, but it is not known to contain all of NP. The relationship between BQP and the classical classes remains poorly understood, and it raises the possibility that the physical laws governing computation might affect the complexity landscape in ways that the classical theory did not anticipate.
The enduring achievement of complexity theory is not the resolution of its central questions but the framework it has built for asking them. The field has produced a rich and precise vocabulary for discussing computational difficulty, a web of reductions connecting thousands of problems, and a set of techniques—diagonalization, circuits, logical characterizations, interactive proofs—that reveal different facets of the same underlying phenomenon. Its open problems are not failures but the organizing questions of the discipline, and the partial results obtained in pursuit of them have reshaped our understanding of what computation is and what it can accomplish.