Complexity Zoo Introduction
This page is an introduction to the Complexity Zoo which was originally created at http://www.complexityzoo.com/ by Scott Aaronson.
I created the Complexity Zoo with three audiences in mind.
First, me. Before my zookeeping foray, I spent a week trying to put AM outside QMA relative to an oracle, only to learn that this followed trivially from two known results: that of Vereshchagin [Ver92] that AM is outside PP relative to an oracle, and that of Kitaev and Watrous (unpublished, but mentioned in [Wat00]) that QMA is in PP. What to do next? One option would be to work on putting SZK outside QMA relative to an oracle. But instead I decided that, before hoisting one more brick onto the vast edifice of complexity, I'd do well to take stock of what was already known. Some theorists seem able to hold in their minds, in one instant, the results of every FOCS, STOC, and Complexity paper ever published. Not every proof, of course - but those can be looked up if one knows the results and to whom they're due.
I am not one of those theorists. The sprawling web of known relations among complexity classes - containments, oracle separations, random oracle separations, lowness results, the occasional inequality - is not fixed in my memory like the English language. And so it's largely for my own benefit that I recorded a chunk of what's known in one unwieldy HTML file.
The second audience is other theorists and theory students, who might find the Zoo to have a few advantages as a reference. First, inspired by Eric Weisstein's famed World of Mathematics, it links liberally between entries. Second, it can be updated regularly - much of its current content is not yet in any book as far as I know. Third, it takes a democratic approach to complexity classes, with big hitters like NP listed alongside the lesser-known mAL, PODN, and QACC0. Any class is fair game so long as something nontrivial has been said about it in the literature.
The third audience comprises programmers, mathematicians, physicists, and anyone else who bumps into complexity classes occasionally. With this audience in mind I've kept the writing informal; those who need a precise definition of a class should consult the references. I hope that non-theorists, even if they don't understand everything, will at least find some amusement in the many exotic beasts that complexity theory has uncovered.
Comments, corrections, and additions (of classes, results, references...) are most welcome; send to aaronson at ias dot edu.
Recommended Further Reading
- Computational Complexity (1994) by C. H. Papadimitriou. The standard text, and an ideal starting place for beginners.
- "A Catalog of Complexity Classes" (1990) by D. S. Johnson (Chapter 2 in the Handbook of Theoretical Computer Science, Volume A). Close in spirit to the Zoo.
- The Complexity Theory Companion (2002), by L. A. Hemaspaandra and M. Ogihara. A lively guide to structural complexity. Has a "Rogues' Gallery" of classes at the end, including such obscure zoo denizens as US and SFk (though Prof. Hemaspaandra emphasizes to me that the book is "mostly about NP, PH, etc. - pretty normal, standard stuff").
- Lance Fortnow's Computational Complexity Web Log. Includes a 'Complexity Class of the Week.'
Other Theory Compendia
- Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) by M. R. Garey and D. S. Johnson.
- A Compendium of NP Optimization Problems, web site by P. Crescenzi and V. Kann et al.
- NP-Completeness Columns by D. S. Johnson, review articles published in Journal of Algorithms and ACM Trans. Algorithms