Skip to main content
v2026.11,986 entries · CC-BY 4.0

Complexity Zoo: What It Is and How to Look Up a Class

The Complexity Zoo wiki catalogues 553 complexity classes. Learn to find a class, read an entry and use its reference keys.

Written and maintained by CASRAI Editorial Board

Published

On this page

The Complexity Zoo is a wiki that catalogues computational complexity classes: for each class it gives a definition, the known relationships to other classes, and references to the papers behind them. Its main page states that it holds 553 classes and counting (read 2026-11-15), organised alphabetically by class name, and it is a convenient lookup when a paper uses a class such as BQP, PH or AM that you need to place relative to P and NP.

Ask CASRAI · free to tryQuestion about this guide? Ask CASRAI answers with linked sources. 2 free questions a day, no account.

Ask your first question freeSubscribe

What the Complexity Zoo is used for in research

Researchers use the Zoo as a reference, not as a textbook. If a paper claims a problem is in BPP, or complete for some class you have not met, the Zoo entry tells you in a paragraph what the class means, what it contains, what contains it, and which results are known or only relative to an oracle. Each entry carries bracketed reference keys (for example [Edm65] or [Sho97]) that point to the original papers, so the Zoo works as a map to the primary literature rather than a substitute for it. For the underlying ideas of time, space and reductions, start with the computational complexity guide and return to the Zoo when you need a specific class. For a neighbouring area of theoretical computer science, see the computational geometry guide.

Who maintains it and where it lives

The main page names Scott Aaronson as Zookeeper, Greg Kuperberg as Veterinarian, Oliver Habryka as Zoo Conservationist on behalf of the LessWrong community, and Kunal Marwaha as Grunt. It records that the Zoo first opened in 2002, became a wiki in 2005, and was hosted at the University of Waterloo from 2012 to 2020. It is currently served at complexityzoo.net.

Access: the official site only

The Zoo is a public MediaWiki site at complexityzoo.net and needs no account to read. The entry point is the main page, Complexity_Zoo, which lists classes under Symbols and A to Z. Letter pages carry the entries themselves, for example Complexity_Zoo:P, Complexity_Zoo:N and Complexity_Zoo:B. Editing requires signing up, as described on the main page. Use the official site rather than mirrors, because the class count and entries change as contributors edit.

Step by step: look up a complexity class

  1. Open the main page at complexityzoo.net and note the letter row (Symbols, A to Z) and the three lists of related classes: Communication Complexity, Hierarchies and Nonuniform.
  2. Go to the letter page for the class name. The Zoo alphabetises by the class name as tagged, so BQP is under B and NP under N.
  3. Find the class heading, which has the form name, colon, expansion: for example “P : Polynomial-Time” or “BPP : Bounded-Error Probabilistic Polynomial-Time”.
  4. Read the definition paragraph first, then the containments and conditional results that follow it.
  5. Follow the See also links to related classes, and use the reference keys to find the source paper on the Zoo References page.
  6. If you need a gentler route into a class, check the Petting Zoo or the Complexity Garden (described below).

Reading a Zoo entry: three worked examples

Every entry is short prose with a consistent anatomy: a definition, then what the class contains and is contained in, then results that depend on assumptions or oracles, each tied to a reference key. The three entries below show the pattern.

P

The entry defines P as the class of decision problems solvable in polynomial time by a Turing machine. It names linear programming [Kha79], maximum matching in a general graph [Edm65] and primality testing [AKS02] as members. It also defines P-complete: a problem in P to which every problem in P reduces in logarithmic space, with circuit evaluation as the canonical example. Subclasses listed include L, NL, NC and SC, and generalizations include BPP and BQP.

NP

NP is defined as decision problems solvable by a nondeterministic polynomial-time Turing machine, or equivalently problems whose “yes” answers have polynomial-length proofs that can be verified in polynomial time. The entry uses satisfiability (SAT) as its example, since a satisfying assignment proves a “yes” answer. NP-complete means in NP with every NP problem reducing to it, with the foundational results credited to Cook [Coo71], Karp [Kar72] and Levin [Lev73].

BQP

BQP is the class of decision problems solvable in polynomial time by a quantum Turing machine with error at most 1/3, equivalently by uniform polynomial-size quantum circuits [Yao93]. The entry notes that it contains factoring and discrete logarithm [Sho97] and credits the definition to [BV97].

Two further entries show how the Zoo records results that depend on assumptions. The L entry defines logarithmic space as the problems solvable by a Turing machine whose memory use, not counting the input, is logarithmic in the input size n, notes that L is contained in P, and records Reingold’s result [Rei04] that L = SL, so undirected graph connectivity is solvable in deterministic logarithmic space. The BPP entry defines the class by acceptance probabilities (at least 2/3 of paths accept for “yes”, at most 1/3 for “no”), records that it is contained in Σ2P ∩ Π2P [Lau83], and states conditional results such as: if any problem in E requires circuits of size 2^Ω(n), then BPP = P [IW97].

Output and how to read it

The “output” of a lookup is a definition plus a web of relationships. Read three things in order. First, the definition: is the class defined over decision problems, languages or functions, and with what resource bound and error bound? Second, containments: statements like “L is contained in P” are inclusions, not strict separations, and many strictness questions are open. Third, conditions: phrases such as “if BPP contains NP” or “relative to an oracle” mark results that do not hold unconditionally. Reference keys in square brackets, such as [Edm65] in the P entry, identify the source papers listed on the Zoo References page.

Citing the Zoo

For a claim that matters in your own work, cite the original paper behind the reference key, and cite the Zoo only for the pointer. When you do cite the Zoo itself, give the entry URL, the access date, and, if you quote the size, the class count shown on the main page at that time (553 on 2026-11-15), because the wiki changes. The general mechanics of reference lists are covered in the bibliography dictionary entry.

Troubleshooting

The class you need is not on the letter page

Classes are alphabetised by tag name, so check the Symbols page for classes beginning with non-letters. The main page also links Communication Complexity, Hierarchies and Nonuniform lists, which gather related classes outside the alphabetical order.

Some descriptive pages show no text

The Zoo links an Introductory Essay, a Contributor’s Guide and a Conventions and Notation page from its main page. If one of these does not load, use the main page itself, the Zoo Glossary, which explains terms that theoretical computer scientists use without defining, and the Pronunciation Guide instead.

An entry seems incomplete or wrong

The Zoo is a community wiki. The main page invites readers to sign up, click the edit links and include references or links to papers, to add new classes alphabetically, to add them to the relevant Template:CZ letter table of contents and to increment the total. Treat unreferenced statements with caution and verify them in the cited paper.

Companion pages and free alternatives

All Zoo pages are free to read. The data table below lists the navigation pages named on the main page and what each is for.

Resource What it offers When to use it
Petting Zoo A gentler version of the Zoo with fewer classes; self-contained, needing only the terms alphabet, word and language First contact with P, NP, PH, PSPACE, BPP, BQP and similar classes
Complexity Garden Rigorously defined computational problems of interest and their inclusions When you start from a problem, not a class
Complexity Zoology A computer-assisted survey by Greg Kuperberg with inclusion diagrams To see how classes sit relative to each other
Zoo Glossary Terms used by theoretical computer scientists without definition When entry wording is unfamiliar

Textbooks and the primary papers cited by the reference keys remain the authoritative source for proofs. Note that the Petting Zoo is marked “Under construction”, so expect gaps.

Frequently asked questions

What is the Complexity Zoo?

It is a wiki of computational complexity classes, started in 2002 and made a wiki in 2005, with 553 classes listed on its main page at the time of reading.

Who runs the Complexity Zoo?

The main page names Scott Aaronson as Zookeeper and Greg Kuperberg as Veterinarian, with Oliver Habryka acting for the LessWrong community and Kunal Marwaha as Grunt.

Is the Zoo suitable for beginners?

The main page points newcomers to the Petting Zoo, a gentler version with fewer classes that needs only the notions of alphabet, word and language.

Can I add or correct a class?

Yes. Sign up, use the edit links, include references or links to papers, and follow the alphabetical and table-of-contents conventions given on the main page.

Should I cite the Zoo or the original paper?

Cite the original paper for any result you rely on; use the Zoo’s reference keys to find it, and cite the Zoo only as a pointer, with the date you read it.

Sources

  • Complexity Zoo main page, https://complexityzoo.net/Complexity_Zoo (read 2026-11-15)
  • Petting Zoo, https://complexityzoo.net/Petting_Zoo (read 2026-11-15)
  • Complexity Zoo entries for P, NP, BQP, L and BPP, https://complexityzoo.net/Complexity_Zoo:P, :N, :B and :L (read 2026-11-15)
  • Complexity Garden, https://complexityzoo.net/Complexity_Garden (read 2026-11-15)
  • Zoo Glossary, https://complexityzoo.net/Zoo_Glossary (read 2026-11-15)

Data: Complexity Zoo navigation pages and their stated purpose

Compiled from the Complexity Zoo main page and the pages it links, listing each companion resource with the purpose the Zoo itself states for it, as read on 2026-11-15.

Period covered: 2026.

Complexity Zoo navigation pages and their stated purpose
PageStated purposeEntry type
Petting ZooGentler version of the Zoo with fewer classes for newcomers; needs only alphabet, word, languageIntroduction
Complexity GardenRigorously defined computational problems of interest and their inclusionsProblem catalogue
Complexity DojoMajor theorems of complexity theoryTheorem list
Special ExhibitClasses of quantum states and probability distributionsClass list
Complexity ZoologyComputer-assisted survey by Greg Kuperberg with inclusion diagramsSurvey
Zoo GlossaryTerms used by theoretical computer scientists without definitionGlossary

Sources

Compiled by CASRAI from the sources above. Free to reuse under CC BY 4.0 with attribution.

Follow CASRAI

Research-administration guidance, standards updates and independent tool reviews.

Ask CASRAI · free to try

Ask about Complexity Zoo: What It Is and How to Look Up a Class

2 free questions a day, no account.

An AI assistant for research: funder rules, compliance, methods and publishing. It links the sources behind its answers and labels answers that come from a web search.

Answers draw on CASRAI's guides and dictionary plus the federal and funder documents we index: Federal Register, Grants.gov, Regulations.gov and UKRI.

Works on this site and inside Claude, Cursor and the AI tools you already use.

Everything CASRAI publishes — this page, the dictionary, the guides and the news — stays open to read, with no account and no card.

Referenced across the research world

University of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logoUniversity of Cambridge logoColumbia University logoCrossref logoUniversity of Edinburgh logoHarvard University logoUniversity of Oxford logoPrinceton University logoStanford School of Medicine logoUniversity College London logoORCID logo
  • University of Cambridge logo
  • Columbia University logo
  • Crossref logo
  • University of Edinburgh logo
  • Harvard University logo
  • University of Oxford logo
  • Princeton University logo
  • Stanford School of Medicine logo
  • University College London logo
  • ORCID logo

View CASRAI adoption →