## Introduction

Welcome to the **Complexity Zoo**… There are now 535 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

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-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 –

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 –

BP_{d}(P) –

BPE –

BPEE –

BP_{H}SPACE(f(n)) –

BPL –

BPNP –

BPP –

BPP^{cc} –

BPP_{}^{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]} –

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_{}(f(n)) –

HeurP –

HeurPP –

HeurNTIME_{}(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*[2,1] –

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 –

NONE –

NNC(f(n)) –

NP –

NPC –

NP_{C} –

NP^{cc} –

NP_{}^{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 –

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_{}^{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 –

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 –

QPLIN –

QPSPACE –

QRG –

QRG(k) –

QRG(2) –

QRG(1) –

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_{}^{cc} –

RPP –

RQP –

RSPACE(f(n))

### S

S_{2}P –

S_{2}-EXPP^{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-P –

SPARSE –

SPL –

SPP –

SQG –

SUBEXP –

symP –

SZK –

SZK_{h}

### T

TALLY –

TC^{0} –

TFNP –

Θ_{2}P –

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] –

XP –

XP_{uniform}

### Y

### Z

ZAM^{cc} –

ZBQP –

ZK –

ZPE –

ZPP –

ZPP^{cc} –

ZPTIME(f(n)) –

ZQP