Scott Aaronson’s Complexity Zoo: A Knowledge System for the Hardest Problems in Computing

From P vs NP to quantum complexity, Scott Aaronson’s sprawling reference, and working Map of Computational Complexity tracks the strange boundaries of what computers can and cannot do.

Complexity theory, also known as computational complexity, is the radical core of theoretical computer science that studies the inherent difficulty of algorithmic problems by identifying the “tipping point of resources” required to solve them.

Scott Aaronson’s Complexity Zoo is a living reference system for computational complexity theory. Its real value is not just that it catalogs hundreds of complexity classes, but that it maps the relationships between them — containments, equalities, oracle separations, complete problems, and major open questions — across classical, randomized, interactive, counting, circuit, quantum, parameterized, and algebraic complexity.

Complexity theory, specifically known as computational complexity, is a foundational area of theoretical computer science. At its core, it is the study of computational resources and the inherent difficulty of solving different algorithmic problems.

Rather than just asking if a problem can be solved by a computer, complexity theory asks how much time, memory, or steps are required to solve it. The field contrasts computationally “easy” problems — like multiplying numbers, which computers can do efficiently using a relatively small number of steps — with “hard” problems where the required time grows exponentially as the input gets larger. For these highly complex problems, computers might be forced to rely on an exhaustive search of all possible answers, which is practically impossible for large inputs.

This study of computational limits is considered a “radical core of computer science” because it has massive real-world implications. Most notably, modern cryptography and the security of the internet rely entirely on complexity theory; our digital security systems are built on the foundational belief that certain tasks, like factoring enormous numbers, are fundamentally too hard for computers to solve quickly.

To organize the massive landscape of computational problems, theoretical computer scientists group problems into complexity classes. A complexity class is essentially a category of problems that share a similar “tipping point of resources” required to solve them. The field has discovered hundreds of different classes — such as P, NP, BPP, and PSPACE — which form a “sprawling web of known relations” including mathematical containments and inequalities. Catalogs like the Complexity Zoo were created specifically to keep track of these hundreds of exotic classes and the resources they represent.

https://complexityzoo.net/Complexity_Zoo

Scott Aaronson’s Complexity Zoo is playful on the surface and severe underneath. It is not a textbook. It is not merely a glossary. It is a long-running attempt to keep theoretical computer science from dissolving into a pile of disconnected acronyms. What the Zoo catalogs are not just classes — P, NP, PSPACE, BQP, #P, **MIP***, and hundreds more — but the relations among them: containments, equalities, oracle separations, lowness results, complete problems, and the odd theorem that suddenly makes an entire corner of the subject snap into focus.[1][2][3]

Aaronson says the project began with three audiences in mind. First, himself. He wanted a way to keep track of the “sprawling web” of known relations instead of rediscovering facts that were already in the literature. Second, theorists and students who needed a reference that linked entries liberally and could be updated faster than books. Third, mathematically literate outsiders — programmers, mathematicians, physicists — who run into complexity classes often enough to need a map, even if they are not going to live inside the subject full time.[1] That triple aim explains the Zoo’s peculiar tone. It is informal on purpose, but not casual about the mathematics.

It also explains the Zoo’s politics, if that is the word. Aaronson’s own description is “democratic”: the famous beasts stand next to the obscure ones, and obscurity is not a disqualifier. NP gets its page, obviously. So do classes like mAL, PODN, and QACC⁰, because the point is not prestige. The point is whether the literature has said something nontrivial.[1]

Two Zoos, really

In practice there are two versions of the project. The first is the living wiki, the one still online now. Its front page says the Zoo first opened in 2002, turned into a wiki in 2005, and was hosted at the University of Waterloo from 2012 to 2020. It currently advertises 551 classes and counting, invites public contributions, and names Greg Kuperberg as “Veterinarian” and Oliver Habryka, on behalf of the LessWrong community, as “Zoo Conservationist.”[2]

The second is the LaTeX/PDF translation prepared by Chris Bourke. That PDF is historically valuable because it freezes the Zoo at an earlier moment. Its cover still says 417 classes and counting, and its contents run from “About This Document” through the introductory essay, pronunciation guide, the main class catalog, a special exhibit on quantum states and probability distributions, acknowledgements, and a bibliography.[3] Bourke’s preface is unusually clear about what he thought he was doing: turning the website into a PDF, preserving its links, and “spruc[ing] up the cages” in LaTeX.[3]

That split matters. The wiki is the live organism. The PDF is the fossil record. In fact, the current main page now says Bourke’s LaTeX version is obsolete as a live reference, which is just a blunt way of admitting what the report already implied: the PDF is best used as a snapshot, not as the canonical current edition.[2][3]

How the place is laid out

The Zoo is built for browsing. The main page leads with alphabetical indices — Symbols, A–Z — and then with side collections such as Communication Complexity, Hierarchies, and Nonuniform. It also points readers toward the Introductory Essay, the more beginner-friendly Petting Zoo, the Complexity Dojo, and the Special Exhibit on classes of quantum states and probability distributions. The structure is loose, but not random. It nudges you from one entry to its neighbors until the subject starts to look less like a dictionary and more like a web.[1][2][6]

That cross-linking was deliberate from the beginning. Aaronson cites Eric Weisstein’s World of Mathematics as a model: don’t just define things, wire them together.[1] Bourke’s PDF preserves that spirit with color-coded hyperlinks — red for internal jumps, green for bibliography entries, magenta for external URLs — so even the supposedly static version behaves a bit like hypertext.[3]

Then there are the appendices, which tell you a lot about the kind of project this is. The Pronunciation Guide gives practical advice for saying things like #P (“sharp-P”), ⊕L (“parity-L”), and P/poly (“P slash poly”), which sounds like trivia until you remember how often complexity theory gets taught and argued out loud.[4] The Special Exhibit splits off a separate “phylum” for classes of quantum states and probability distributions — AmpP, ΨP, Tree, Vidal, and the tensor/sum hierarchy — partly because Aaronson did not want the main Zoo to look biased toward his own quantum-state interests.[5] Even that little gesture is revealing. The Zoo is not only about decision problems. It is also about the complexity of representations.

The field the Zoo is trying to show you

One of the best things about the Zoo is that it quietly corrects a beginner’s mistake. Complexity theory is not one ladder from easy to hard. It is a pile of different measuring sticks laid across the same underlying problems. Time. Space. Randomness. Interaction. Counting. Circuit depth and size. Advice. Approximation guarantees. Parameters. Average-case distributions. Quantum mechanics. Algebraic structure. Change the resource, and the class changes with it.[3][5]

So the familiar backbone — L, NL, P, NP, PH, PSPACE, EXP, NEXP — is only the start. The Zoo records the deterministic and nondeterministic spine of the subject, but it also keeps the structural theorems that make that spine meaningful: NL = coNL; AL = P; AP = PSPACE; IP = PSPACE; MIP = NEXP.[3] Those are not decorative facts. They are the moments when apparently different models of computation turn out to be the same beast in another cage.

Randomness changes the picture again. The Zoo tracks the now-standard trio RP, coRP, and ZPP, then the wider class BPP, together with the derandomization story that shadows it. The report is right to stress that proving BPP = P is not just a housekeeping result. In the Zoo’s presentation, it sits close to hard lower-bound territory, which is why it remains a structural question rather than a minor cleanup.[3]

Interaction changes it more dramatically. MA and AM live between witness-checking and full interactive proof. IP swallows the polynomial hierarchy and turns out to be exactly PSPACE. MIP jumps all the way to NEXP. And MIP — multi-prover interaction with entangled provers — is where the historical difference between the PDF and the live wiki becomes impossible to ignore. In the PDF snapshot, the relation between MIP and NEXP is described as completely unknown. On the current wiki, the page states the 2020 theorem *MIP = RE**.[2][3][18]

Counting classes give the Zoo another axis. #P is what happens when “does there exist a witness?” becomes “how many witnesses are there?” From there you get PP, AWPP, the counting hierarchy, and one of the subject’s most famous bridges: PH ⊆ P^#P. The Zoo is especially good here because it makes the classical counting story and the quantum story touch. BQP ends up inside P^#P, PP, and AWPP, even while it contains factoring and discrete logarithm via Shor’s algorithm.[3][15][16][17]

Circuit classes and nonuniform classes pull the field in a different direction. AC⁰, ACC⁰, TC⁰, and P/poly are not just alternate notations for the same thing; they ask what happens when you care about depth, threshold gates, modular gates, or advice strings rather than Turing-machine time. The Zoo’s treatment of ACC⁰ is worth lingering on. It frames the class as a lower-bound frontier: too weak to feel general, too strong for the known methods to break open comfortably.[3]

And then there are the regions that do not fit the usual survey course but absolutely belong in the atlas: PTAS, FPTAS, APX for approximation; FPT, W[1], and XP for parameterized complexity; AvP and DistNP for average-case complexity; VPₖ and VNPₖ for Valiant’s algebraic analogue of the P versus NP story.[3] The Zoo’s breadth is not an affectation. It is the point.

Figure 1. A schematic relation map for representative classes discussed in the report. Solid arrows indicate canonical containments; dashed links mark equalities or especially tight identifications emphasized in the Zoo. Adapted from the source report’s diagram and the class relations summarized in the live Zoo and the Bourke PDF snapshot. [2][3]

The results that keep showing up

A reference work becomes useful when it helps you tell which theorems are load-bearing. The Zoo is full of those. Cook–Levin turns satisfiability into the first canonical NP-complete problem. Valiant turns counting into its own world with #P. Chandra–Kozen–Stockmeyer tie alternation to P and PSPACE. Immerman and Szelepcsényi show that nondeterministic logspace is closed under complement. Lund–Fortnow–Karloff–Nisan and Shamir make interactive proofs central instead of peripheral. Babai–Fortnow–Lund connect multi-prover proofs to nondeterministic exponential time. Toda forces the polynomial hierarchy through counting. Adleman–DeMarrais–Huang and Fortnow–Rogers pin down upper bounds for BQP. Shor makes quantum polynomial time impossible to shrug off. Then Ji–Natarajan–Vidick–Wright–Yuen blow the roof off with *MIP = RE**.[3][7][8][9][10][11][12][13][14][15][16][17][18]

Table 1. The landmark results singled out in the source report. The table preserves the report’s chronology but replaces repeated bracket numbering with one clean source label per row. [3][7][8][9][10][11][12][13][14][15][16][17][18]

Figure 2. The same milestones rendered as a schematic timeline. The point is not that every theorem sits on one neat track, because they do not; the point is that these are the results the report treats as the field’s recurring anchor points. [3][7][8][9][10][11][12][13][14][15][16][17][18]

That last result, MIP = RE, is the cleanest proof that the live wiki and the old PDF do different jobs. In the snapshot, MIP is a question mark. In the live Zoo, it is a settled landmark. So if you want to know what the field looked like when a problem was still open, the PDF is perfect. If you want the current shape of the cage, use the wiki.[2][3][18]

Representative classes, without the citation clutter

The original report included a large comparison table. It was useful, but the citation tags made it harder to read than it had to be. Here it is again in three rendered panels, with the underlying sources consolidated instead of repeated line by line.

Table 2. Panel 1 covers the deterministic, nondeterministic, and space-bounded backbone of the subject. [2][3]

Table 3. Panel 2 covers randomized and interactive classes, where witness-checking turns into dialogue and, eventually, into entangled multi-prover protocols. [2][3]

Table 4. Panel 3 covers counting, quantum, circuit, approximation, and parameterized classes — the parts of the Zoo that make it clear this is not just a guide to P versus NP. [2][3][5]

What the Zoo does well, and what it does not

The Zoo is unusually good at showing relationships. That sounds obvious until you compare it to ordinary textbooks. A textbook has to teach in order. The Zoo does not. It can put graph isomorphism, AWPP, QMA, TC⁰, and DistNP on neighboring mental shelves if the mathematics says they belong there. For research, that matters. It reduces the chance that you spend a week proving something that was already a trivial corollary of two older results Aaronson did not happen to remember either.[1][3]

It is also good at scale. The field is too broad now for a clean canon. The Zoo accepts that and keeps going. The result is messy, yes, but productively messy. A project like this earns its value when it lets you move from a famous class to a barely remembered one without falling through the floor.

But there are limits. The Zoo is not a substitute for definitions written with full formal care, and it says so. Entries are informal. Reduction notions are not always foregrounded. Oracle results, random-oracle results, and unrelativized theorems can sit uncomfortably close together if you are not watching. The PDF even jokes about this with a warning not to “feed oracles” to the complexity classes. Funny line. Real caution.[3]

And the PDF snapshot, for all its charm, really is a snapshot. That is why it is so valuable historically and so risky if you forget what it is. The more a corner of the field has moved, the more you need the live wiki.[2][3]

How to use the Zoo without getting lost

If you are new, do not start by clicking randomly through the A page. Start with the Introductory Essay. Then move to the Petting Zoo, which collects the “Most Important Classes” and explains why they matter before you try to absorb the long tail.[1][6] From there, a sensible route is to get the basic deterministic and nondeterministic story straight — P, NP, coNP, NP-complete, PH, PSPACE — then add randomness (RP, ZPP, BPP), interaction (MA, AM, IP), counting (#P, PP), and only after that move outward into quantum, approximation, parameterization, average-case work, and the algebraic analogues.

For systematic study, the Zoo itself points readers toward Papadimitriou’s Computational Complexity, David Johnson’s “A Catalog of Complexity Classes,” Hemaspaandra and Ogihara’s The Complexity Theory Companion, Lance Fortnow’s computational complexity weblog, and Garey and Johnson on NP-completeness.[1][3][19][20][21][22][23] That reading list tells you something important. The Zoo is most powerful when you use it as a map and switchboard — a place to orient yourself, chase a relation, and then go back to the underlying paper or textbook for the full theorem.

In that sense the Zoo is a very old-fashioned scholarly tool wearing a very strange costume. It does not make complexity theory tidy. It makes the mess legible. For a subject built out of partial containments, conjectured separations, historical accidents, and one theorem after another that rewrites the shape of the map, that is more than enough.

References

[1] Scott Aaronson, “Complexity Zoo Introduction,” Complexity Zoo, accessed 14 April 2026. https://complexityzoo.net/Zoo_Intro

[2] “Complexity Zoo,” Complexity Zoo main page, accessed 14 April 2026. https://complexityzoo.net/Complexity_Zoo

[3] Scott Aaronson, The Complexity Zoo. LaTeX translation by Chris Bourke. PDF translation of ComplexityZoo.com. https://cse.unl.edu/~cbourke/latex/ComplexityZoo.pdf

[4] “Complexity Zoo Pronunciation Guide,” Complexity Zoo, accessed 14 April 2026. https://complexityzoo.net/Complexity_Zoo_Pronunciation_Guide

[5] “Complexity Zoo Exhibit: Classes of Quantum States and Probability Distributions,” Complexity Zoo, accessed 14 April 2026. https://complexityzoo.net/Zoo_Exhibit

[6] “Petting Zoo,” Complexity Zoo, accessed 14 April 2026. https://complexityzoo.net/Petting_Zoo

[7] Stephen A. Cook, “The Complexity of Theorem-Proving Procedures,” Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971.

[8] Leslie G. Valiant, “The Complexity of Computing the Permanent,” Theoretical Computer Science 8, 1979.

[9] Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer, “Alternation,” Journal of the ACM 28, no. 1, 1981.

[10] Neil Immerman, “Nondeterministic Space is Closed under Complement,” SIAM Journal on Computing 17, no. 5, 1988; Róbert Szelepcsényi, “The Method of Forced Enumeration for Nondeterministic Automata,” 1987.

[11] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan, “Algebraic Methods for Interactive Proof Systems,” FOCS, 1990.

[12] Adi Shamir, “IP = PSPACE,” FOCS, 1990. Mirror: https://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/Shamir-IP%3DPSPACE.pdf

[13] László Babai, Lance Fortnow, and Carsten Lund, “Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols,” Computational Complexity 1, 1991.

[14] Seinosuke Toda, “On the Computational Power of PP and ⊕P,” FOCS, 1991.

[15] Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang, “Quantum Computability,” SIAM Journal on Computing 26, no. 5, 1997.

[16] Lance Fortnow and John D. Rogers, “Complexity Limitations on Quantum Computation,” CCC, 1998; journal version 1999.

[17] Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing 26, no. 5, 1997.

[18] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, *“MIP = RE,”** 2020. https://arxiv.org/abs/2001.04383

[19] Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

[20] David S. Johnson, “A Catalog of Complexity Classes,” in Handbook of Theoretical Computer Science, Volume A, 1990.

[21] Lane A. Hemaspaandra and Mitsunori Ogihara, The Complexity Theory Companion, Springer, 2002.

[22] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

[23] Lance Fortnow, Computational Complexity Web Log. https://fortnow.com/lance/complog/