These pages are from a computer-assisted analysis of known relations among complexity classes. The list of complexity classes is taken from the Complexity Zoo, the living survey of complexity classes created by Scott Aaronson. (It's now a public wiki, but Scott did most of the work.)
I have gotten indispensable help and encouragement with this project from Scott Aaronson, Lance Fortnow, Bryan Bell, and — last but not least — "Monty Polynomial-Time", the resident robozoologist.
Please send corrections or additions (especially resolutions of blank cases) to Greg Kuperberg.
Some of the classes in the Zoo are not suitable for this Zoology project because they are not decision classes ( e.g., #P) or the class is parameterized (e.g., ZPTIME(f(n)) ), or for other reasons. Also a few classes have been added, and every asymmetric class A comes with coA and A ∩ coA.
Each listed class comes with specific decisions concerning uniformity and oracle access. As a result, certain separations come too cheaply; they dodge the real issues. Some classes (such as REG and PBP) do not take oracles, although this is not noted presently on the "Properties" page. The rule for space classes is that oracle queries are bounded by max(poly,space).
Unlike in the Zoo, circuit classes are taken as uniform with respect to spot DLOGTIME verification. (This is a careful definition that is recognized as the right one among circuit experts.) A few circuit classes are made non-uniform with polynomial advice.
This material is based upon work supported by the National Science Foundation under Grant Nos. 0306681 and 0606795.
