[Math] How many Complexity Classes do you know

computational complexity

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?

Best Answer

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

Related Question