View source for Complexity Zoo Introduction

''This page is an introduction to the [[Complexity Zoo]] which was originally created at http://www.complexityzoo.com/ by [[Scott Aaronson]].''

<hr>

I created the Complexity Zoo with three audiences in mind.  

First, me.  Before my zookeeping foray, I spent a week trying to put {{zcls|a|am}} outside {{zcls|q|qma}} relative to an oracle, only to learn that this followed trivially from two known results: that of Vereshchagin [[Zoo References#ver92|[Ver92]]] that {{zcls|a|am}} is outside {{zcls|p|pp}} relative to an oracle, and that of Kitaev and Watrous (unpublished, but mentioned in [[Zoo References#wat00|[Wat00]]]) that {{zcls|q|qma}} is in {{zcls|p|pp}}.  What to do next?  One option would be to work on putting {{zcls|s|szk}} outside {{zcls|q|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 [http://mathworld.wolfram.com 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 {{zcls|n|np}} listed alongside the lesser-known {{zcls|m|mal|mAL}}, {{zcls|p|podn}}, and {{zcls|q|qacc0|QACC<sub>0</sub>}}.  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==
*[[Zoo References#pap94|<i>Computational Complexity</i>]] (1994) by C. H. Papadimitriou.  The standard text, and an ideal starting place for beginners. 
*[[Zoo References#joh90|"A Catalog of Complexity Classes"]] (1990) by D. S. Johnson (Chapter 2 in the <i>Handbook of Theoretical Computer Science</i>, Volume A).  Close in spirit to the Zoo. 
*[[Zoo References#ho02|<i>The Complexity Theory Companion</i>]] (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 [[Complexity Zoo:U#us|US]] and [[Complexity Zoo:S#sfk|SF<sub>k</sub>]] (though Prof. Hemaspaandra emphasizes to me that the book is "<i>mostly</i> about [[Complexity Zoo#np|NP]], [[Complexity Zoo#ph|PH]], etc. - pretty normal, standard stuff"). 
*Lance Fortnow's [http://fortnow.com/lance/complog/ Computational Complexity Web Log].  Includes a 'Complexity Class of the Week.'

==Other Theory Compendia==
*[[Zoo References#gj79"|<i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i>]] (1979) by M. R. Garey and D. S. Johnson. 
*[http://www.nada.kth.se/~viggo/wwwcompendium/ A Compendium of NP Optimization Problems], web site by P. Crescenzi and V. Kann et al.
*[http://public.research.att.com/~dsj/columns/ NP-Completeness Columns by D. S. Johnson], review articles published in Journal of Algorithms and ACM Trans. Algorithms
[[Category:Computational Complexity]]