Introduction

Welcome to the Complexity Zoo… There are now 535 classes and counting!

what’s your problem?

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

This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators:

Zookeeper 
Scott Aaronson
Veterinarian 
Greg Kuperberg
Tour Guide 
Christopher Granade

In 2012, this content was moved again to the University of Waterloo and is maintained there by

Zoo Conservationist 
Vincent Russo

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

Appendices

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-NPC
1NAuxPDAp
2-EXP
3SUM-hard
#AC0
#L
#L/poly
#GA
#P
#W[t]
⊕EXP
⊕L
⊕L/poly
⊕P
⊕Pcc
⊕SAC0
⊕SAC1

A

A0PP
AC
AC0
AC0[m]
AC1
ACC0
AH
AL
ALL
ALOGTIME
AlgP/poly
Almost-NP
Almost-P
Almost-PSPACE
AM
AMcc
AMEXP
AM ∩ coAM
AM[polylog]
AmpMP
AmpP-BQP
AP
APP
APX
ATIME
AUC-SPACE(f(n))
AuxPDA
AVBPP
AvgE
AvgP
AW[P]
AWPP
AW[SAT]
AW[*]
AW[t]
AxP
AxPP

B

βP
BC=P
BH
BPd(P)
BPE
BPEE
BPHSPACE(f(n))
BPL
BP•NP
BPP
BPPcc
BPPkcc
BPPKT
BPP/log
BPP/mlog
BPP//log
BPP/rlog
BPP-OBDD
BPPpath
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
BQPCTC
BQPtt/poly
BQTIME(f(n))
k-BWBP

C

C=AC0
C=L
C=P
CC
CC0
CFL
CLOG
CH
Check
CL#P
CkP
CNP
coAM
coC=P
cofrIP
Coh
coMA
coModkP
compIP
compNP
coNE
coNEXP
coNL
coNP
coNPcc
coNP/poly
coNQP
coRE
coRNC
coRP
coSL
coSPARSE
coUCC
coUP
CP
cq-Σ2
CSIZE(f(n))
CSL
CSP
CZK

D

D#P
DCFL
Δ2P
δ-BPP
δ-RP
DET
DiffAC0
DisNP
DistNP
DP
DQC1
DQP
DSPACE(f(n))
DTIME(f(n))
DTISP(t(n),s(n))
Dyn-FO
Dyn-ThC0

E

E
EE
EEE
EESPACE
EEXP
EH
ELEMENTARY
ELkP
EP
EPTAS
k-EQBP
EQP
EQPK
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(t(n))
FOLL
FP
FPNP[log]
FPR
FPRAS
FPT
FPTnu
FPTsu
FPTAS
FQMA
frIP
F-TAPE(f(n))
F-TIME(f(n))

G

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

H

HalfP
HeurBPP
HeurBPTIME(f(n))
HeurDTIMEdelta(f(n))
HeurP
HeurPP
HeurNTIMEdelta(f(n))
HkP
HVSZK

I

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

L

L
LC0
LH
LIN
LkP
LOGCFL
LogFew
LogFewNL
LOGLOG
LOGNP
LOGSNP
L/poly
LWPP

M

MA
MAcc
MA’
MAC0
MAE
MAEXP
mAL
MAPOLYLOG
MaxNP
MaxPB
MaxSNP
MaxSNP0
mcoNL
MinPB
MIP
MIP*[2,1]
MIPns
MIPEXP
(Mk)P
mL
MM
MMSNP
mNC1
mNL
mNP
ModkL
ModL
ModkP
ModP
ModZkL
mP
MP
MPC
mP/poly
mTC0

N

NAuxPDAp
NC
NC0
NC1
NC2
NE
NE/poly
Nearly-P
NEE
NEEE
NEEXP
NEXP
NEXP/poly
NIPZK
NIQSZK
NISZK
NISZKh
NL
NL/poly
NLIN
NLO
NLOG
NONE
NNC(f(n))
NP
NPC
NPC
NPcc
NPkcc
NPI
NP ∩ coNP
(NP ∩ coNP)/poly
NP/log
NPMV
NPMV-sel
NPMVt
NPMVt-sel
NPO
NPOPB
NP/poly
(NP,P-samplable)
NPR
NPSPACE
NPSV
NPSV-sel
NPSVt
NPSVt-sel
NQP
NSPACE(f(n))
NT
NT*
NTIME(f(n))

O

OptP

P

P
P/log
P/poly
P#P
P#P[1]
PCTC
PAC0
PBP
k-PBP
PC
Pcc
Pkcc
PCD(r(n),q(n))
P-Close
PCP(r(n),q(n))
PDQP
PermUP
PEXP
PF
PFCHK(t(n))
PH
PHcc
Φ2P
PhP
Π2P
PINC
PIO
PK
PKC
PL
PL1
PL
PLF
PLL
PLS
PNP
PNPcc
P||NP
PNP[k]
PNP[log]
PNP[log^2]
P-OBDD
PODN
polyL
PostBPP
PostBPPcc
PostBQP
PP
PPcc
PP/poly
PPA
PPAD
PPADS
PPP
PPP
PPSPACE
PQMA[log]
PQUERY
PR
PR
PrHSPACE(f(n))
PromiseBPP
PromiseBQP
PromiseP
PromiseRP
PromiseUP
PrSPACE(f(n))
P-Sel
PSK
PSPACE
PSPACEcc
PSPACE/poly
PT1
PTAPE
PTAS
PT/WK(f(n),g(n))
PZK

Q

Q
QAC0
QAC0[m]
QACC0
QACf0
QAM
QCFL
QCMA
QH
QIP
QIP[2]
QL
QMA
QMA-plus
QMA(2)
QMA1
QMAlog
QMAM
QMA/qpoly
QMIP
QMIPle
QMIPne
QNC
QNC0
QNCf0
QNC1
QP
QPLIN
QPSPACE
QRG
QRG(k)
QRG(2)
QRG(1)
QSZK

R

R
RBQP
RE
REG
RevSPACE(f(n))
RG
RG[1]
RHL
RHSPACE(f(n))
RL
RNC
RP
RPcc
RPkcc
RPP
RQP
RSPACE(f(n))

S

S2P
S2-EXP•PNP
SAC
SAC0
SAC1
SAPTIME
SBP
SBPcc
SBQP
SC
SE
SEH
SelfNP
SFk
Σ2P
SKC
SL
SLICEWISE PSPACE
SNP
SO
SO(Horn)
SO(Krom)
SO(LFP)
SO(TC)
SO[t(n)]
SP
span-P
SPARSE
SPL
SPP
SQG
SUBEXP
symP
SZK
SZKh

T

TALLY
TC0
TFNP
Θ2P
TreeBQP
TREE-REGULAR

U

UAMcc
UAP
UCC
UCFL
UE
UL
UL/poly
UP
UPcc
UPostBPPcc
UPPcc
US
USBPcc
UWAPPcc

V

VCk
VCOR
VNCk
VNPk
VPk
VPL
VQPk

W

W[1]
WAPP
WAPPcc
WHILE
W[P]
WPP
W[SAT]
W[*]
W[t]
W*[t]

X

XOR-MIP*[2,1]
XP
XPuniform

Y

YACC
YP
YPP
YQP

Z

ZAMcc
ZBQP
ZK
ZPE
ZPP
ZPPcc
ZPTIME(f(n))
ZQP



Source link