Complexity Zoo

The Complexity Zoo is a living catalog of computational complexity classes — the hundreds of distinct resource-bound categories that classify what can and cannot be computed under various constraints of time, space, randomness, quantum coherence, nondeterminism, and interaction. Originally created by Scott Aaronson in 2005 as a pedagogical tool and maintained as a collaborative reference, the Zoo documents the extraordinary taxonomic proliferation that has occurred since the foundational definitions of P and NP.

The Menagerie

The canonical classes form the spine of the Zoo. P (deterministic polynomial time), NP (nondeterministic polynomial time), PSPACE (polynomial space), BPP (bounded-error probabilistic polynomial time), and BQP (bounded-error quantum polynomial time) are the big cats — the classes that attract the most attention and funding. But around them swarms a vast ecosystem of finer distinctions.

PH (Polynomial Hierarchy) captures problems solvable with a bounded number of alternating quantifiers — a tower of complexity that generalizes NP and co-NP. PP (Probabilistic Polynomial time) captures problems where a randomized algorithm answers correctly with probability strictly greater than 1/2. #P captures counting problems — not whether a solution exists, but how many — and is believed to be strictly harder than NP. NL (Nondeterministic Logarithmic space) and L (Deterministic Logarithmic space) probe the boundary of computation with severely constrained memory.

More exotic inhabitants include IP (Interactive Polynomial time), which equals PSPACE; MIP (Multi-Prover Interactive), which equals NEXP; SZK (Statistical Zero Knowledge), for problems whose solutions can be verified without revealing the solution itself; and QMA (Quantum Merlin-Arthur), the quantum analogue of NP. Each class is defined by a precise resource bound, and the map of containments, equalities, and incomparabilities is the research frontier of the field.

Why So Many Classes?

The proliferation of complexity classes is not a failure of taste. It is the natural consequence of a productive abstraction. The resource-bound framework — classify problems by the resources required to solve them — is so general that it generates endless refinement. For every combination of time, space, randomness, quantumness, nondeterminism, interaction, and approximation, there is a class. The framework is powerful enough to classify almost anything, and therefore classifies far more than anyone strictly needs.

From a systems-theoretic perspective, this proliferation is a case study in the dynamics of classification itself. A productive taxonomy generates new distinctions faster than it generates understanding of their relations. The Zoo grows because the definitional apparatus is easier to operate than the proof apparatus: defining a new class requires only a resource bound and a machine model; proving its relationship to existing classes requires techniques that may not exist. The result is a catalog whose entries outnumber its theorems.

The Zoo as Epistemic Structure

The Complexity Zoo is not merely a reference. It is an epistemic institution — a shared map that orients research, shapes funding priorities, and establishes what counts as a result. A problem's classification determines which community studies it, which conferences accept papers about it, and which funding agencies consider it relevant. The Zoo is a social technology as much as a mathematical one.

This raises a question that the Zoo itself does not ask: when does classification become its own form of knowledge? When the map contains more detail than the territory, the map ceases to be a tool for navigation and becomes a territory of its own. The Zoo's hundreds of classes are not all equally well-understood. Many have no known natural problems, no complete problems, and no known relationships to their neighbors. They are defined but uninhabited — mathematical species whose existence has been posited but never observed.

The Complexity Zoo is the periodic table of computation, and like the periodic table it organizes known elements while pointing to gaps where new ones should exist. But unlike chemistry, complexity theory cannot synthesize its missing elements. The periodic table was validated by the discovery of gallium and germanium; the Zoo awaits a validation that may never come, because its central question — whether P equals NP — has resisted fifty years of inquiry not because the answer is hidden, but because we do not know what mathematics would recognize it. The Zoo is a beautiful catalog of a continent that may be larger than our maps can ever chart.