# Difference between revisions of "Complexity Zoo"

m |
m (→Introduction) |
||

(22 intermediate revisions by 14 users not shown) | |||

Line 1: | Line 1: | ||

− | + | __NOTOC__ | |

+ | |||

+ | ==Introduction== | ||

+ | |||

+ | Welcome to the '''Complexity Zoo'''... There are now 545 classes and counting! | ||

+ | [[Image:zoo.gif|thumb|right|200px|what's your problem?]] | ||

+ | |||

+ | {{CZ-Menu-Content}} | ||

+ | |||

+ | ; Zookeeper : [http://www.scottaaronson.com/ Scott Aaronson] | ||

+ | ; Veterinarian : [http://www.math.ucdavis.edu/~greg/ Greg Kuperberg] | ||

+ | ; Zoo Conservationist : [https://www.linkedin.com/in/oliver-habryka-8a585297 Oliver Habryka] on behalf of the [https://www.lesswrong.com/ LessWrong] community | ||

+ | |||

+ | The Zoo first opened in 2002. It was made into a wiki in 2005, and hosted at the University of Waterloo from 2012 to 2020. | ||

+ | |||

+ | Errors? Omissions? Misattributions? Your favorite class not here? Then please contribute to the zoo as you see fit by [[Special:UserLogin | signing up]] and clicking on the edit links. Please include references, or better yet links to papers if available. | ||

+ | |||

+ | To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.) Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our [[Help:Contents | simple wiki help page]]. | ||

+ | |||

+ | If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson.com. | ||

+ | |||

+ | ==See Also== | ||

+ | |||

+ | ''Introductory Resources'' | ||

+ | * [[Zoo Intro|Introductory Essay]]: New visitors may want to stop here and see what the Zoo is all about. | ||

+ | * [[Petting Zoo]]: A more gentle version of the Zoo with fewer classes, meant for new initiates in complexity. (If you're looking for where the Most Important Classes went, look in the Petting Zoo.) | ||

+ | |||

+ | ''Other Collections and Resources'' | ||

+ | * [[Complexity Garden]]: Problems of interest in complexity theory and some notes about important inclusions. | ||

+ | * [[Complexity Dojo]]: A collection of major theorems in complexity theory. | ||

+ | * [[Zoo Exhibit|Special Exhibit]]: A collection of classes of quantum states and probability distributions. | ||

+ | * [http://www.math.ucdavis.edu/~greg/zoology/intro.html Complexity Zoology]: A computer-assisted survey maintained by the [http://www.math.ucdavis.edu/~greg/ Greg Kuperberg], including [http://www.math.ucdavis.edu/~greg/zoology/diagram.xml active] and [http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf static] inclusion diagrams. | ||

+ | * [http://satoshihada.wordpress.com/complexity-zoo-for-ipad/ Complexity Zoo for iPad (and iPhone)]: An iOS viewer for Complexity Zoo. | ||

+ | |||

+ | ''Appendices'' | ||

+ | *[[Zoo Glossary|Glossary]]: Definitions of some complexity theoretic terms. | ||

+ | *[[Zoo References|References]]: Bibliography for the Zoo. | ||

+ | *[[Zoo Pronunciation|Pronunciation Guide]]: A resource for those who insist on communicating verbally about complexity. | ||

+ | *[[Zoo Conventions|Conventions and Notation]]: Common notational conventions used here at the Zoo. | ||

+ | *[[Zoo Operators|Operators]]: A (very short) list of operators which act upon classes. | ||

+ | *[[Zoo Acknowledgments|Acknowledgments]]: Where the Zookeeper and friends acknowledge those who have helped out with the Zoo. | ||

+ | *[[Meta:Complexity Zoo Contributor's Guide|Complexity Zoo Contributor's Guide]]: A guide on how to get started helping out with the Zoo. | ||

+ | |||

+ | ''NB:'' Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram. These references are obsolete until further notice. | ||

+ | |||

+ | <!-- Moved Most Important Classes to Petting Zoo --> | ||

+ | |||

+ | == All Classes == | ||

+ | {{CZ-Menu-Content}} | ||

+ | |||

+ | {{CZ-Letter-Section|Symbols}} | ||

+ | {{CZ-Letter-Section|A}} | ||

+ | {{CZ-Letter-Section|B}} | ||

+ | {{CZ-Letter-Section|C}} | ||

+ | {{CZ-Letter-Section|D}} | ||

+ | {{CZ-Letter-Section|E}} | ||

+ | {{CZ-Letter-Section|F}} | ||

+ | {{CZ-Letter-Section|G}} | ||

+ | {{CZ-Letter-Section|H}} | ||

+ | {{CZ-Letter-Section|I}} | ||

+ | <!--{{CZ-Letter-Section|J}} | ||

+ | {{CZ-Letter-Section|K}}--> | ||

+ | {{CZ-Letter-Section|L}} | ||

+ | {{CZ-Letter-Section|M}} | ||

+ | {{CZ-Letter-Section|N}} | ||

+ | {{CZ-Letter-Section|O}} | ||

+ | {{CZ-Letter-Section|P}} | ||

+ | {{CZ-Letter-Section|Q}} | ||

+ | {{CZ-Letter-Section|R}} | ||

+ | {{CZ-Letter-Section|S}} | ||

+ | {{CZ-Letter-Section|T}} | ||

+ | {{CZ-Letter-Section|U}} | ||

+ | {{CZ-Letter-Section|V}} | ||

+ | {{CZ-Letter-Section|W}} | ||

+ | {{CZ-Letter-Section|X}} | ||

+ | {{CZ-Letter-Section|Y}} | ||

+ | {{CZ-Letter-Section|Z}} | ||

+ | |||

+ | |||

+ | {{CZ-Categories}} |

## Latest revision as of 02:46, 3 December 2020

## Introduction

Welcome to the **Complexity Zoo**... There are now 545 classes and counting!

*Complexity classes by letter:*
Symbols -
A -
B -
C -
D -
E -
F -
G -
H -
I -
J -
K -
L -
M -
N -
O -
P -
Q -
R -
S -
T -
U -
V -
W -
X -
Y -
Z

*Lists of related classes:*
Communication Complexity -
Hierarchies -
Nonuniform

- Zookeeper
- Scott Aaronson
- Veterinarian
- Greg Kuperberg
- Zoo Conservationist
- Oliver Habryka on behalf of the LessWrong community

The Zoo first opened in 2002. It was made into a wiki in 2005, and hosted at the University of Waterloo from 2012 to 2020.

Errors? Omissions? Misattributions? Your favorite class not here? Then please contribute to the zoo as you see fit by signing up and clicking on the edit links. Please include references, or better yet links to papers if available.

To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.) Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our simple wiki help page.

If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson.com.

## See Also

*Introductory Resources*

- Introductory Essay: New visitors may want to stop here and see what the Zoo is all about.
- Petting Zoo: A more gentle version of the Zoo with fewer classes, meant for new initiates in complexity. (If you're looking for where the Most Important Classes went, look in the Petting Zoo.)

*Other Collections and Resources*

- Complexity Garden: Problems of interest in complexity theory and some notes about important inclusions.
- Complexity Dojo: A collection of major theorems in complexity theory.
- Special Exhibit: A collection of classes of quantum states and probability distributions.
- Complexity Zoology: A computer-assisted survey maintained by the Greg Kuperberg, including active and static inclusion diagrams.
- Complexity Zoo for iPad (and iPhone): An iOS viewer for Complexity Zoo.

*Appendices*

- Glossary: Definitions of some complexity theoretic terms.
- References: Bibliography for the Zoo.
- Pronunciation Guide: A resource for those who insist on communicating verbally about complexity.
- Conventions and Notation: Common notational conventions used here at the Zoo.
- Operators: A (very short) list of operators which act upon classes.
- Acknowledgments: Where the Zookeeper and friends acknowledge those who have helped out with the Zoo.
- Complexity Zoo Contributor's Guide: A guide on how to get started helping out with the Zoo.

*NB:* Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram. These references are obsolete until further notice.

## All Classes

*Complexity classes by letter:*
Symbols -
A -
B -
C -
D -
E -
F -
G -
H -
I -
J -
K -
L -
M -
N -
O -
P -
Q -
R -
S -
T -
U -
V -
W -
X -
Y -
Z

*Lists of related classes:*
Communication Complexity -
Hierarchies -
Nonuniform

### Symbols

0-1-NP_{C} -
1NAuxPDA^{p} -
2-EXP -
3SUM-hard -
#AC^{0} -
#L -
#L/poly -
#GA -
#P -
#W[t] -
⊕EXP -
⊕L -
⊕L/poly -
⊕P -
⊕P^{cc} -
⊕SAC^{0} -
⊕SAC^{1}

### A

A_{0}PP -
AC -
AC^{0} -
AC^{0}[m] -
AC^{1} -
ACC^{0} -
AH -
AL -
ALL -
ALOGTIME -
AlgP/poly -
Almost-NP -
Almost-P -
Almost-PSPACE -
AM -
AM^{cc} -
AM_{EXP} -
AM ∩ coAM -
AM[polylog] -
AmpMP -
AmpP-BQP -
AP -
APP -
APSPACE -
APX -
ASPACE -
ATIME -
AUC-SPACE(f(n)) -
AuxPDA -
AVBPP -
AvgE -
AvgP -
AW[P] -
AWPP -
AW[SAT] -
AW[*] -
AW[t] -
AxP -
AxPP

### B

βP -
BC_{=}P -
BH -
BP_{d}(P) -
BPE -
BPEE -
BP_{H}SPACE(f(n)) -
BPL -
BP•NP -
BPP -
BPP^{cc} -
BPP_{$k$}^{cc} -
BPP^{KT} -
BPP/log -
BPP/mlog -
BPP//log -
BPP/rlog -
BPP-OBDD -
BPP_{path} -
BPQP -
BPSPACE(f(n)) -
BPTIME(f(n)) -
BQNC -
BQNP -
BQP -
BQP/log -
BQP/poly -
BQP/mlog -
BQP/mpoly -
BQP/qlog -
BQP/qpoly -
BQP-OBDD -
BQPSPACE -
BQP_{CTC} -
BQP_{tt}/poly -
BQTIME(f(n)) -
k-BWBP

### C

C_{=}AC^{0} -
C_{=}L -
C_{=}P -
CC -
CC^{0} -
CFL -
CLOG -
CH -
Check -
CL#P -
C_{k}P -
CNP -
coAM -
coC_{=}P -
cofrIP -
Coh -
coMA -
coMod_{k}P -
compIP -
compNP -
coNE -
coNEXP -
coNL -
coNP -
coNP^{cc} -
coNP/poly -
coNQP -
coRE -
coRNC -
coRP -
coSL -
coSPARSE -
coUCC -
coUP -
CP -
cq-Σ_{2} -
CSIZE(f(n)) -
CSL -
CSP -
CZK

### D

D#P -
DCFL -
Δ_{2}P -
δ-BPP -
δ-RP -
DET -
DiffAC^{0} -
DisNP -
DistNP -
DP -
DQC1 -
DQP -
DSPACE(f(n)) -
DTIME(f(n)) -
DTISP(t(n),s(n)) -
Dyn-FO -
Dyn-ThC^{0}

### E

E -
EE -
EEE -
EESPACE -
EEXP -
EH -
ELEMENTARY -
EL_{k}P -
EP -
EPTAS -
k-EQBP -
EQP -
EQP_{K} -
EQTIME(f(n)) -
ESPACE -
∃BPP -
∃NISZK -
EXP -
EXP/poly -
EXPSPACE

### F

FBQP -
FERT -
FPERT -
Few -
FewEXP -
FewP -
FH -
FIXP -
FNL -
FNL/poly -
FNP -
FO -
FO(DTC) -
FO(LFP) -
FO(PFP) -
FO(TC) -
FO() -
FOLL -
FP -
FP^{NP[log]} -
FPL -
FPR -
FPRAS -
FPT -
FPT_{nu} -
FPT_{su} -
FPTAS -
FQMA -
frIP -
F-TAPE(f(n)) -
F-TIME(f(n))

### G

GA -
GAN-SPACE(f(n)) -
GapAC^{0} -
GapL -
GapP -
GC(s(n),C) -
GCSL -
GI -
GLO -
GPCD(r(n),q(n)) -
G[t]

### H

HalfP -
HeurBPP -
HeurBPTIME(f(n)) -
HeurDTIME_{$\delta$}(f(n)) -
HeurP -
HeurPP -
HeurNTIME_{$\delta$}(f(n)) -
H_{k}P -
HVSZK

### I

IC[log,poly] - IP - IPP - IP[polylog]

### L

L -
LC^{0} -
LH -
LIN -
L_{k}P -
LOGCFL -
LogFew -
LogFewNL -
LOGLOG -
LOGNP -
LOGSNP -
L/poly -
LWPP

### M

MA -
MA^{cc} -
MA' -
MAC^{0} -
MA_{E} -
MA_{EXP} -
mAL -
MA_{POLYLOG} -
MaxNP -
MaxPB -
MaxSNP -
MaxSNP_{0} -
mcoNL -
MinPB -
MIP -
MIP* -
MIP^{ns} -
MIP_{EXP} -
(M_{k})P -
mL -
MM -
MMSNP -
mNC^{1} -
mNL -
mNP -
Mod_{k}L -
ModL -
Mod_{k}P -
ModP -
ModZ_{k}L -
mP -
MP -
MPC -
mP/poly -
mTC^{0}

### N

NAuxPDA^{p} -
NC -
NC^{0} -
NC^{1} -
NC^{2} -
NE -
NE/poly -
Nearly-P -
NEE -
NEEE -
NEEXP -
NEXP -
NEXP/poly -
NIPZK -
NIQSZK -
NISZK -
NISZK_{h} -
NL -
NL/poly -
NLIN -
NLO -
NLOG -
NMCL -
NONE -
NNC(f(n)) -
NP -
NPC -
NP_{C} -
NP^{cc} -
NP_{$k$}^{cc} -
NPI -
NP ∩ coNP -
(NP ∩ coNP)/poly -
NP/log -
NPMV -
NPMV-sel -
NPMV_{t} -
NPMV_{t}-sel -
NPO -
NPOPB -
NP/poly -
(NP,P-samplable) -
NP_{R} -
NPSPACE -
NPSV -
NPSV-sel -
NPSV_{t} -
NPSV_{t}-sel -
NQL -
NQL -
NQP -
NSPACE(f(n)) -
NT -
NT* -
NTIME(f(n))

### O

### P

P -
P/log -
P/poly -
P^{#P} -
P^{#P[1]} -
P_{CTC} -
PAC^{0} -
PBP -
k-PBP -
P_{C} -
P^{cc} -
P_{$k$}^{cc} -
PCD(r(n),q(n)) -
P-Close -
PCP(r(n),q(n)) -
PDQP -
PermUP -
PEXP -
PF -
PFCHK(t(n)) -
PH -
PH^{cc} -
Φ_{2}P -
PhP -
Π_{2}P -
PINC -
PIO -
P^{K} -
PKC -
PL -
PL_{1} -
PL_{∞} -
PLF -
PLL -
PLS -
P^{NP} -
P^{NPcc} -
P^{||NP} -
P^{NP[k]} -
P^{NP[log]} -
P^{NP[log^2]} -
P-OBDD -
PODN -
polyL -
PostBPP -
PostBPP^{cc} -
PostBQP -
PP -
PP^{cc} -
PP/poly -
PPA -
PPAD -
PPADS -
P^{PP} -
PPP -
PPSPACE -
P^{QMA[log]} -
PQUERY -
PR -
P_{R} -
Pr_{H}SPACE(f(n)) -
PromiseBPP -
PromiseBQP -
PromiseP -
PromiseRP -
PromiseUP -
PrSPACE(f(n)) -
P-Sel -
PSK -
PSPACE -
PSPACE^{cc} -
PSPACE/poly -
PT_{1} -
PTAPE -
PTAS -
PT/WK(f(n),g(n)) -
PZK

### Q

Q -
QAC^{0} -
QAC^{0}[m] -
QACC^{0} -
QAC_{f}^{0} -
QAM -
QCFL -
QCMA -
QCPH -
QH -
QIP -
QIP[2] -
QL -
QMA -
QMA-plus -
QMA(2) -
QMA_{1} -
QMA_{log} -
QMAM -
QMA/qpoly -
QMIP -
QMIP_{le} -
QMIP_{ne} -
QNC -
QNC^{0} -
QNC_{f}^{0} -
QNC^{1} -
QP -
QPH -
QPLIN -
QPSPACE -
QRG -
QRG(k) -
QRG(2) -
QRG(1) -
QRL -
QSZK

### R

R -
RBQP -
RE -
REG -
RevSPACE(f(n)) -
RG -
RG[1] -
R_{H}L -
R_{H}SPACE(f(n)) -
RL -
RNC -
RP -
RP^{cc} -
RP_{$k$}^{cc} -
RPP -
RQP -
RSPACE(f(n))

### S

S^{≠} -
S_{2}P -
S_{2}-EXP•P^{NP} -
SAC -
SAC^{0} -
SAC^{1} -
SAPTIME -
SBP -
SBP^{cc} -
SBQP -
SC -
SE -
SEH -
SelfNP -
SF_{k} -
Σ_{2}P -
SKC -
SL -
SLICEWISE PSPACE -
SNP -
SO -
SO(Horn) -
SO(Krom) -
SO(LFP) -
SO(TC) -
SO[] -
SP -
span-L -
span-P -
SPARSE -
SPL -
SPP -
SQG -
SUBEXP -
symP -
SZK -
SZK_{h}

### T

TALLY -
TC^{0} -
TFNP -
Θ_{2}P -
TI -
Tower -
TreeBQP -
TREE-REGULAR

### U

UAM^{cc} -
UAP -
UCC -
UCFL -
UE -
UL -
UL/poly -
UP -
UP^{cc} -
UPostBPP^{cc} -
UPP^{cc} -
US -
USBP^{cc} -
UWAPP^{cc}

### V

VC_{k} -
VC_{OR} -
VNC_{k} -
VNP_{k} -
VP_{k} -
VPL -
VQP_{k}

### W

W[1] -
WAPP -
WAPP^{cc} -
WHILE -
W[P] -
WPP -
W[SAT] -
W[*] -
W[t] -
W^{*}[t]

### X

XOR-MIP*[2,1] -
XL -
XNL -
XP -
XP_{uniform}

### Y

### Z

ZAM^{cc} -
ZBQP -
ZK -
ZPE -
ZPP -
ZPP^{cc} -
ZPTIME(f(n)) -
ZQP