MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We can read about the main complexity classes in textbooks and online in Wikipedia:

However, in papers, there are a lot of important new classes which are rarely found, such as $\textsf{PPAD}$.

How many complexity classes do you know? Could you please give a diagram to show the relations between them?

share|cite|improve this question
My advisor tells me: This zoo contains only Lists of related classes: Communication Complexity - Hierarchies - Nonuniform – Rupei Xu Mar 6 '14 at 7:34
I think the above comment was supposed to be attached to Joel David Hamkins's answer. In any case, I am not sure I understand it. Does the complexity zoo omit certain kinds of classes that you are interested in? If so, can you give an example? PPAD, for example, is in the zoo. Or maybe the diagram does not provide the kind of information about interrelationships that you want? – Timothy Chow Mar 6 '14 at 19:44
@Timothy Chow, Yes, you are right. This comment was supposed to reply to Joel David Hamkins. I know PPAD, I am just wondering how many complexity classes are known and the whole picture of them(the diagram of the total complexity classes known). – Rupei Xu Mar 6 '14 at 20:34
@RupeiXu, My understanding is that the Complexity Zoo aims to be comprehensive, and furthermore is open to submissions of new classes, and wiki-style editing of the current information by knowledgeable participants. So if there are classes missing, then you can document that and contribute them. – Joel David Hamkins Mar 7 '14 at 13:10

See the Complexity Zoo, which seems to aim at being current. It currently lists 495 classes, including PPAD, as you mention, and a large diagram of some of the classes.

enter image description here

share|cite|improve this answer
Does anyone know how to include a thumbnail image of the diagram? It is a pdf file. – Joel David Hamkins Mar 6 '14 at 2:04
Done, I let you re-size if needed! – Franck Dernoncourt Mar 6 '14 at 5:37
The image looks vaguely like a person sitting on a throne. – Monroe Eskew Mar 6 '14 at 6:47
@FranckDernoncourt, Thanks very much! – Joel David Hamkins Mar 6 '14 at 11:47
Is there an origin? Is there something from which everything comes, in the diagram? – Erin Carmody Mar 7 '14 at 2:52

The top part of the Computability Zoo (r.e., recursive, and beyond) is covered in more detail in the Computability Menagerie.

enter image description here

share|cite|improve this answer
Thanks. Then, what is the connection between the diagram of this and the one above? Is there a uniform one? – Rupei Xu Mar 6 '14 at 7:40
Everything in the computability menagerie is way, way above everything in the complexity zoo. – Noah Schweber Mar 6 '14 at 7:57
This one looks like a fairly decent spaceship. – PreferenceBean Mar 6 '14 at 11:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.