How many Complexity Classes do you know?

Question

We can read about the main complexity classes in textbooks and online in Wikipedia: http://en.wikipedia.org/wiki/Computational_complexity_theory

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?

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 06 '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). — , Mar 06 '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 07 '14 at 13:10

score 22 · Answer 1 · edited Mar 06 '14 at 06:13

22

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

edited Mar 06 '14 at 06:13

Franck Dernoncourt

103

answered Mar 06 '14 at 01:45

Joel David Hamkins

224,022

Does anyone know how to include a thumbnail image of the diagram? It is a pdf file. – Joel David Hamkins Mar 06 '14 at 02:04
Done, I let you re-size if needed! – Franck Dernoncourt Mar 06 '14 at 05:37
12

The image looks vaguely like a person sitting on a throne. – Monroe Eskew Mar 06 '14 at 06:47
@FranckDernoncourt, Thanks very much! – Joel David Hamkins Mar 06 '14 at 11:47
Is there an origin? Is there something from which everything comes, in the diagram? – Mar 07 '14 at 02:52

Bjørn Kjos-Hanssen · Answer 2 · 2014-03-06T06:44:15.050

10

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

edited Mar 06 '14 at 06:44

answered Mar 06 '14 at 02:09

Bjørn Kjos-Hanssen

24,629

Thanks. Then, what is the connection between the diagram of this and the one above? Is there a uniform one? – Mar 06 '14 at 07:40
1

Everything in the computability menagerie is way, way above everything in the complexity zoo. – Noah Schweber Mar 06 '14 at 07:57
3

This one looks like a fairly decent spaceship. – Lightness Races in Orbit Mar 06 '14 at 11:32
Is this amazing diagram accessible somewhere? – Ville Salo Nov 22 '21 at 08:22
@VilleSalo it seems to be inaccessible now :( – Bjørn Kjos-Hanssen Nov 22 '21 at 19:54

How many Complexity Classes do you know?

2 Answers2