9
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Timothy Chow
    Commented Mar 6, 2014 at 19:44
  • $\begingroup$ @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). $\endgroup$
    – user39815
    Commented Mar 6, 2014 at 20:34
  • 3
    $\begingroup$ @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. $\endgroup$
    – Joel David Hamkins
    Commented Mar 7, 2014 at 13:10

2 Answers 2

Reset to default
23
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Does anyone know how to include a thumbnail image of the diagram? It is a pdf file. $\endgroup$
    – Joel David Hamkins
    Commented Mar 6, 2014 at 2:04
  • $\begingroup$ Done, I let you re-size if needed! $\endgroup$
    – Franck Dernoncourt
    Commented Mar 6, 2014 at 5:37
  • 12
    $\begingroup$ The image looks vaguely like a person sitting on a throne. $\endgroup$
    – Monroe Eskew
    Commented Mar 6, 2014 at 6:47
  • $\begingroup$ @FranckDernoncourt, Thanks very much! $\endgroup$
    – Joel David Hamkins
    Commented Mar 6, 2014 at 11:47
  • $\begingroup$ Is there an origin? Is there something from which everything comes, in the diagram? $\endgroup$
    – user10290
    Commented Mar 7, 2014 at 2:52
10
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. Then, what is the connection between the diagram of this and the one above? Is there a uniform one? $\endgroup$
    – user39815
    Commented Mar 6, 2014 at 7:40
  • 1
    $\begingroup$ Everything in the computability menagerie is way, way above everything in the complexity zoo. $\endgroup$
    – Noah Schweber
    Commented Mar 6, 2014 at 7:57
  • 3
    $\begingroup$ This one looks like a fairly decent spaceship. $\endgroup$
    – Lightness Races in Orbit
    Commented Mar 6, 2014 at 11:32
  • $\begingroup$ Is this amazing diagram accessible somewhere? $\endgroup$
    – Ville Salo
    Commented Nov 22, 2021 at 8:22
  • $\begingroup$ @VilleSalo it seems to be inaccessible now :( $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Nov 22, 2021 at 19:54

You must log in to answer this question.