Complexity Zoo

Welcome to a modified version of Complexity Zoo.

There are now 601 classes.

Created by Satoshi Hada. I will welcome any comment.

Last Updated: 2025-02-27 02:08:32 +0000

Motivation

Take for example the result MA=NEXP if and only if NEXP in P/poly. Which class do you think mentions this result? The answer is NEXP (as of April 21, 2011). Neither MA nor P/poly does. So if you visit NEXP, you can find it, otherwise, you can’t. However, those who are interested in MA or P/poly should be able to find the important result. For this purpose, given a class, this modified version displays not only the class itself but also other classes having links to the class. For example, if you visit MA, it displays not only MA but also NEXP so that you can find the result.

Complexity Ranking

This is a ranked list of complexity classes. The score of a class is the number of classes whose decription has a link to the class.

RankClassScore
1P : Polynomial-Time143
2NP : Nondeterministic Polynomial-Time135
3BPP : Bounded-Error Probabilistic Polynomial-Time63
4PSPACE : Polynomial-Space54
5PH : Polynomial-Time Hierarchy45
6P/poly : Nonuniform Polynomial-Time42
7BQP : Bounded-Error Quantum Polynomial-Time40
8EXP : Exponential Time38
9PP : Probabilistic Polynomial-Time36
10L : Logarithmic Space33
11NL : Nondeterministic Logarithmic-Space27
12NEXP : Nondeterministic EXP24
13MA : Merlin-Arthur23
14#P : Sharp-P or Number-P22
15QMA : Quantum MA20
16DTIME(f(n)) : Deterministic f(n)-Time19
17AM : Arthur-Merlin19
18coNP : Complement of NP19
19E : Exponential Time With Linear Exponent18
20FP : Function Polynomial-Time17
21SZK : Statistical Zero Knowledge17
22RP : Randomized Polynomial-Time17
23IP : Interactive Proof Systems16
24AC0 : Unbounded Fanin Constant-Depth Circuits16
25NC1 : Level 1 of NC15
26NC : Nick's Class15
27ZPP : Zero-Error Probabilistic Polynomial-Time15
28FPT : Fixed-Parameter Tractable14
29DSPACE(f(n)) : Deterministic f(n)-Space14
30UP : Unambiguous Polynomial-Time13
31Σ2P : NP With NP Oracle12
32NE : Nondeterministic E11
33ModkP : Mod-k Polynomial-Time11
34FO : First-Order logic11
35EQP : Exact Quantum Polynomial-Time10
36NP ∩ coNP : 9
37FNP : Function NP9
38TC0 : Constant-Depth Threshold Circuits9
39MIP : Multi-Prover Interactive Proof9
40⊕P : Parity P9
41Pcc : Communication Complexity P8
42C=P : Exact-Counting Polynomial-Time8
43NTIME(f(n)) : Nondeterministic f(n)-Time8
44BQP/mpoly : BQP With Polynomial-Size Deterministic Merlin-Like Advice8
45PNP[log] : P With Log NP Queries8
46NEE : Nondeterministic EE8
47NP/poly : Nonuniform NP8
48DET : Determinant7
49EE : Double-Exponential Time With Linear Exponent7
50NPcc : Communication Complexity NP7
51PPcc : Communication Complexity PP7
52S2P : Second Level of the Symmetric Hierarchy7
53PTAS : Polynomial-Time Approximation Scheme7
54k-PBP : Polynomial-Size Width-k Branching Program7
55Δ2P : P With NP Oracle7
56RE : Recursively Enumerable Languages7
57PPA : Polynomial Parity Argument7
58QIP : Quantum IP7
59SO : Second-Order logic6
60NC2 : Level 2 of NC6
61Π2P : coNP With NP Oracle6
62coNEXP : Complement of NEXP6
63NPC : NP-Complete6
64NPO : NP Optimization6
65SNP : Strict NP6
66BQP/qpoly : BQP With Polynomial-Size Quantum Advice6
67BPEE : Bounded-Error Probabilistic EE6
68TFNP : Total Function NP6
69W[1] : Weighted Analogue of NP6
70AWPP : Almost WPP6
71AC : Unbounded Fanin Polylogarithmic-Depth Circuits6
72SBP : Small Bounded-Error Probability6
73AC1 : Unbounded Fanin Log-Depth Circuits6
74W[t] : Nondeterministic Fixed-Parameter Hierarchy6
75BPL : Bounded-Error Probabilistic L6
76LOGCFL : Logarithmically Reducible to CFL6
77mP : Monotone P6
78R : Recursive Languages6
79SL : Symmetric Logarithmic-Space5
80APX : Approximable5
81NC0 : Level 0 of NC5
82CH : Counting Hierarchy5
83QSZK : Quantum Statistical Zero-Knowledge5
84ModkL : Mod-k L5
85mNL : Monotone NL5
86PZK : Perfect Zero Knowledge5
87BPPpath : Threshold BPP5
88RNC : Randomized NC5
89NQP : Nondeterministic Quantum Polynomial-Time5
90FewP : NP With Few Witnesses5
91EH : Exponential-Time Hierarchy With Linear Exponent5
92PC : Polynomial-Time Over The Complex Numbers5
93PPAD : Polynomial Parity Argument (Directed)5
94SPP : Stoic PP5
95BPPcc : Communication Complexity BPP5
96VPk : Valiant P Over Field k5
97coNE : Complement of NE5
98PR : Polynomial-Time Over The Reals5
99LWPP : Length-Dependent Wide PP5
100AP : Alternating P5
101UPPcc : Unrestricted Communication Analogue of PP5
102coNPcc : Complement of NPcc5
103PPP : Polynomial Pigeonhole Principle5
104WPP : Wide PP4
105RG(2) : Two-turn (one-round) Refereed Games4
106YP : Your Polynomial-Time or Yaroslav-Percival4
107O2P : Second Level of the Oblivious Symmetric Hierarchy4
108PBP : Polynomial-Size Branching Program4
109FO[] : Iterated First-Order logic4
110NISZK : Non-Interactive SZK4
111P-OBDD : Polynomial-Size Ordered Binary Decision Diagram4
112QIP[2] : 2-Message Quantum IP4
113BP•L : Bounded-Error Probabilistic L with Two Way Access to Randomness4
114GapL : Gap Logarithmic-Space4
115NSPACE(f(n)) : Nondeterministic f(n)-Space4
116CFL : Context-Free Languages4
117PostBQP : BQP With Postselection4
118QNC : Quantum NC4
119PLS : Polynomial Local Search4
120coAM : Complement of AM4
121PR : Primitive Recursive Functions4
122frIP : Function-Restricted IP Proof Systems4
123MaxSNP : Maximization SNP4
124P-Sel : P-Selective Sets4
125QP : Quasipolynomial-Time4
126NPC : NP Over The Complex Numbers4
127W[P] : Weighted Circuit Satisfiability4
128mNC1 : Monotone NC14
129P#P : P With #P Oracle4
130W[SAT] : Weighted Satisfiability4
131#L : Sharp-L4
132RL : Randomized Logarithmic-Space4
133PHcc : Communication Complexity PH4
134AM[polylog] : AM With Polylog Rounds4
135mL : Monotone L4
136CZK : Computational Zero-Knowledge4
137ACC0 : AC0 With Arbitrary MOD Gates4
138XP : Fixed-Parameter Tractable for Each Parameter4
139APP : Amplified PP4
140SC : Steve's Class4
141FNL : Function NL3
142QMIP : Quantum Multi-Prover Interactive Proofs3
143NPMV : NP Multiple Value3
144BQP/poly : BQP With Polynomial-Size Karp-Lipton Advice3
145AmpMP : Amplifiable MP3
146PromiseBPP : Promise-Problem BPP3
147NPSV : NP Single Value3
148EXPSPACE : Exponential Space3
149ELEMENTARY : Finitely Iterated Exponential Time3
150NPR : NP Over The Reals3
151MIP* : MIP With Quantum Provers3
152⊕L : Parity L3
153NEEXP : Nondeterministic EEXP3
154NQL : Nondet Quasi-Linear3
155FPTAS : Fully Polynomial-Time Approximation Scheme3
156FBQP : Function BQP3
157para- : Parameterized Complexity3
158EEXP : Double-Exponential Time3
159MAEXP : Exponential-Time MA3
160AvgP : Average Polynomial-Time3
161GapP : Gap Polynomial-Time3
162UL : Unambiguous L3
163QAC0[m] : Quantum AC0[m]3
164AMcc : Communication Complexity AM3
165L/poly : Nonuniform Logarithmic Space3
166QACC0 : Quantum ACC03
167PL : Probabilistic L3
168NPMVt : NPMV Total3
169RG(k) : k-turn Refereed Games3
170BPP/mlog : BPP With Logarithmic Deterministic Merlin-Like Advice3
171PostBPPcc : Communication Complexity PostBPP3
172DiffAC0 : Difference #AC03
173YQP* : Yaroslav BQP star3
174XPuniform : Uniform XP3
175PPADS : Polynomial Parity Argument (Directed, Sink)3
176coC=P : Complement of C=P3
177SQG : Short Quantum Games3
178PPSPACE : Probabilistic PSPACE3
179WAPP : Weak Almost-Wide PP3
180DistNP : Distributional NP3
181coRE : Complement of RE3
182MaxPB : MaxNP Polynomially Bounded3
183PNP : P With Oracle Access To NP3
184ZBQP : Strict Quantum ZPP3
185QRG(k) : k-turn Quantum Refereed Games3
186Pcc:Pcc in NOF model, players3
187FO(TC) : First-order with transitive closure3
188RG : Refereed Games3
189TALLY : Tally Languages3
190QRG(2) : Two-turn (one-round) Quantum Refereed Games3
191ONP : Oblivious NP3
192S2-EXP•PNP : Don't Ask3
193SPARSE : Sparse Languages3
194BPTIME(f(n)) : Bounded-Error Probabilistic f(n)-Time3
195MP : Middle-Bit P3
196BH : Boolean Hierarchy Over NP3
197coRP : Complement of RP3
198QNC0 : Quantum NC03
199QMA(2) : Quantum MA With Multiple Certificates3
200VNPk : Valiant NP Over Field k3
201AC0[m] : AC0 With MOD m Gates3
202P||NP : P With Parallel Queries To NP3
203XL : Fixed-Parameter Logspace for Each Parameter3
204BPSPACE(f(n)) : Bounded-Error Probabilistic f(n)-Space3
205mcoNL : Complement of mNL3
206ModPH : Modular Counting Hierarchy3
207DCFL : Deterministic CFL3
208QRG : Quantum Refereed Games2
209#AC0 : Sharp-AC02
210RG(1) : One-turn Refereed Games2
211MMSNP : Monadic Monotone SNP2
212QRL : Quantum Regular Languages2
213PPP : P With PP Oracle2
214CP : Continuous P2
215QMIPne : Quantum Multi-Prover Interactive Proofs With No Prior Entanglement2
216BPP-OBDD : Polynomial-Size Bounded-Error Ordered Binary Decision Diagram2
217mNP : Monotone NP2
218BPP/rlog : BPP With Logarithmic Probabilistically Sampled Random Advice2
219ZP•L : Zero-Error Probabilistic L with Two Way Access to Randomness2
220QMA/qpoly : QMA With Polynomial-Size Quantum Advice2
221TC : Threshold Circuits2
222NPI : NP-Intermediate2
223ESPACE : Exponential Space With Linear Exponent2
224PCD(r(n),q(n)) : Probabilistically Checkable Debate2
225QACf0 : QAC0 With Fanout2
226LOGSNP : Logarithmically-Restricted SNP2
227NEXP/poly : Nonuniform NEXP2
228REG : Regular Languages2
229MAC0 : Majority of AC02
230TOWER : Iterated Exponential Time2
231QNCf0 : Quantum NC0 With Unbounded Fanout2
232QMA-plus : QMA With Super-Verifier2
233LOGNP : Logarithmically-Restricted NP2
234NL/poly : Nonuniform NL2
235PCP(r(n),q(n)) : Probabilistically Checkable Proof2
236ZK : Zero-Knowledge (see CZK)2
237SAPTIME : Stochastic Alternating Polynomial-Time2
238UCFL : Unambiguous CFL2
239QAC0 : Quantum AC02
240UL/poly : Nonuniform UL2
241PromiseP : Promise-Problem P2
242MAE : Exponential-Time MA With Linear Exponent2
243BQP/qlog : BQP With Logarithmic-Size Quantum Advice2
244AW[SAT] : Alternating W[SAT]2
245NPcc:NPcc in NOF model, players2
246NPSPACE : Nondeterministic PSPACE2
247HeurDTIME(f(n)) : Heuristic DTIME2
248ALL : The Class of All Languages2
249GPCD(r(n),q(n)) : Generalized Probabilistically Checkable Debate2
250AW[*] : Alternating W[*]2
251NPOPB : NPO Polynomially Bounded2
252PDQP : Product Dynamical Quantum Polynomial time2
253NPSVt : NPSV Total2
254Coh : Coherent Languages2
255k-EQBP : Width-k Polynomial-Time Exact Quantum Branching Programs2
256MaxNP : Maximization NP2
257Check : Checkable Languages2
258GapAC0 : Gap #AC02
259BPd(P) : Polynomial Size d-Times-Only Branching Program2
260FO(PFP) : First-order with partial fixed point2
261(NP,P-samplable) : Average NP With Samplable Distributions2
262RBQP : Strict Quantum RP2
263RPcc:Randomized Pcc2
264XNL : Fixed-Parameter Nondeterministic Logspace for Each Parameter2
265NAuxPDAp : Nondeterministic Auxiliary Pushdown Automata2
266QL : Quasi-Linear2
267compNP : Competitive NP Proof System2
268IC[log,poly] : Logarithmic Instance Complexity, Polynomial Time2
269YP* : Yaroslav-Percival Star2
270AL : Alternating L2
271βP : Limited-Nondeterminism NP2
272DQP : Dynamical Quantum Polynomial-Time2
273∃BPP : BPP With Existential Operator2
274coNL : Complement of NL2
275FOLL : First-Order log log n2
276BPE : Bounded-Error Probabilistic E2
277GA : Graph Automorphism2
278ZQP : Zero-Error Extension Of EQP2
279YPP : Yaroslav BPP2
280QPH : Quantum PH2
281PNPcc : Communication Complexity PNP2
282GI : Graph Isomorphism2
283QRG(1) : One-turn Quantum Refereed Games2
284RQP : One-sided Error Extension of EQP2
285SBPcc : Communication Complexity SBP2
286Almost-P : Languages Almost Surely in PA2
287LkP : Low Hierarchy In NP2
288FO(LFP) : First-order with least fixed point2
289YQP : Yaroslav BQP2
290BQP/mlog : BQP With Logarithmic-Size Deterministic Merlin-Like Advice2
291BPHSPACE(f(n)) : Bounded-Error Halting Probabilistic f(n)-Space2
292coUP : Complement of UP2
293⊕Pcc : Communication Complexity ⊕P2
294Few : FewP With Flexible Acceptance Mechanism2
295PT1 : Polynomial Threshold Functions2
296BPPcc:BPPcc in NOF model, players2
297Q : Quasi-Realtime Languages2
298AxP : Approximable in Polynomial Time2
299A0PP : One-Sided Analog of AWPP2
300P/log : P With Logarithmic Advice2
301PNP[k] : P With k NP Queries(for constant k)1
302PINC : Polynomial Ignorance of Names of Classes1
303CSPACE : Catalytic space1
304MAcc : Communication Complexity MA1
305WLC0 : Unbounded Fanin Linear Size (wires) Constant-Depth Circuits1
306NNLT : Nondeterministic Nearly Linear Time1
307CSL : Context Sensitive Languages1
308polyL : Polylogarithmic Space1
309CkP : kth Level of CH1
310CL : Catalytic Logspace1
311PIO : Polynomial Input Output1
312AMEXP : Exponential-Time AM1
313W[*] : Union of W[t]'s1
314SO(Krom) : Second-order in Krom form1
315CSP : Constraint Satisfaction Problems1
316OptP : Optimum Polynomial-Time1
317SEH : Strong Exponential Hierarchy1
318XOR-MIP*[2,1] : MIP*[2,1] With 1-Bit Proofs1
319EESPACE : Double-Exponential Space With Linear Exponent1
320QPLIN : Linear Quasipolynomial-Time1
321NT : Near-Testable1
322RevSPACE(f(n)) : Reversible f(n)-Space1
323P#P[1] : P With Single Query To #P Oracle1
324BPP/log : BPP With Logarithmic Karp-Lipton Advice1
325W*[t] : W[t] With Parameter-Dependent Depth1
326mP/poly : Monotone P/poly1
327QCMA : Quantum Classical MA1
3282-EXP : Double-Exponential Time1
329PKC : Perfect Knowledge Complexity1
330BQTIME(f(n)) : Bounded-Error Quantum f(n)-Time1
331C=AC0 : Exact-Counting AC01
332BPP//log : BPP With Logarithmic Randomness-Dependent Advice1
333QCFL : Quantum CFL1
334TC1 : Log-depth Threshold Circuits1
335ModZkL : Restricted ModkL1
336PrHSPACE(f(n)) : Unbounded-Error Halting Probabilistic f(n)-Space1
337C=L : Exact-Counting L1
338DP or Dp : Difference Polynomial-Time1
339HVPZK : Honest-Verifier PZK1
340MinPB : MinNP Polynomially Bounded1
341TreeBQP : BQP Restricted To Tree States1
342NISZKh : NISZK With Limited Help1
343HeurBPTIME(f(n)) : Heuristic BPTIME(f(n))1
344VQPk : Valiant QP Over Field k1
345PAC0 : Probabilistic AC01
346LC0 : Unbounded Fanin Linear Size (gates) Constant-Depth Circuits1
347ALOGTIME : Logarithmic time alternating RAM1
348coSPARSE : Complement of SPARSE1
349GCSL : Growing CSL1
350FPR : Fixed-Parameter Randomized1
351HeurP : Heuristic P1
352FERT : Fixed Error Randomized Time1
353WHILE : While programs and some restrictions1
354SIZE(f(n)) : Circuit Size f(n)1
355QMIPle : Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement1
356SO[LFP] : Second-Order logic with least fixed point1
357GAN-SPACE(f(n)) : Games Against Nature f(n)-Space1
358DTISP(t(n),s(n)) : Simultaneous t(n)-Time and s(n)-Space1
359UE : Unambiguous Exponential-Time With Linear Exponent1
360WAPPcc : Communication Complexity WAPP1
361QCPH : Quantum Classical PH1
362FO(DTC) : First-order with deterministic transitive closure1
363MAPOLYLOG : MA With Polylog Verifier1
364Θ2P : Alternate name for PNP[log]1
365P-RLOCAL : Polylogarithmic rounds in the Randomized LOCAL model1
366HkP : High Hierarchy In NP1
367SelfNP : Self-Witnessing NP1
368PrSPACE(f(n)) : Unbounded-Error Probabilistic f(n)-Space1
369mAL : Monotone AL1
370AVBPP : Average-Case BPP1
371CNP : Continuous NP1
372EP : NP with 2k Accepting Paths1
373PK : P With Kolmogorov-Complexity Oracle1
374VCk : Verification Class With A Circuit of Depth K1
375para-NL : Parameterized Nondeterministic Logspace1
376AxPP : Approximable in Probabilistic Polynomial Time1
377BQP-OBDD : Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram1
378FPERT : Fixed Parameter and Error Randomized Time1
379coRNC : Complement of RNC1
380BPPKT : BPP With Time-Bounded Kolmogorov Complexity Oracle1
381CC0 : Constant-Depth MODm Circuits1
382SZKh : SZK With Limited Help1
383P||QMA : P With Parallel Queries To QMA1
384UCC : Unique Connected Component1
385#L/poly : Nonuniform #L1
386EPTAS : Efficient Polynomial-Time Approximation Scheme1
387⊕SAC1 : AC1 With Unbounded Parity Gates1
388SAC : Semi-Unbounded-Fanin AC1
389δ-BPP : δ-Semi-Random BPP1
390BQP/log : BQP With Logarithmic-Size Karp-Lipton Advice1
391UPostBPPcc : Unrestricted Communication Analogue of PostBPP1
392cofrIP : Complement of frIP1
393MaxSNP0 : Generating Class of MaxSNP1
394mTC0 : Monotone TC01
395LIN : Linear Time1
396OMA : Oblivious MA1
397SBQP : Small Bounded-Error Quantum Polynomial-Time1
398QMA+ : QMA With Non-Negative Amplitudes1
399PermUP : Self-Permuting UP1
400QH : Query Hierarchy Over NP1
401coNQP : Complement of NQP1
402RHL : Randomized Halting Logarithmic-Space1
403AUC-SPACE(f(n)) : Randomized Alternating f(n)-Space1
404RSPACE(f(n)) : Randomized f(n)-Space1
405UPcc : Communication Complexity UP1
406PromiseUP : Promise-Problem UP1
407AH : Arithmetic Hierarchy1
408PQMA[log] : P With Log QMA Queries1
409P-LOCAL : Polylogarithmic rounds in the LOCAL model1
410NIPZK : Non-Interactive PZK1
411EQPK : Exact Quantum Polynomial-Time with Gate Set K1
412NE/poly : Nonuniform NE1
413QNC0/qpoly : Quantum NC0 With Polynomial-Size Quantum Advice1
414NLT : Nearly Linear Time1
415PL : Polynomially-Bounded L-1 Spectral Norm1
416CLOG : Continuous Logarithmic-Time1
417HVSZK : Honest-Verifier SZK1
418MIPEXP : Exponential-Time Multi-Prover Interactive Proof1
419ModP : ModkP With Arbitrary k1
420BPQP : Bounded-Error Probabilistic QP1
421PromiseRP : Promise-Problem RP1
422CSIZE(f(n)) : Circuit Size f(n)1
423VNCk : Valiant NC Over Field k1
424QMAlog : QMA With Logarithmic-Size Proofs1
425F-TIME(f(n)) : Provable DTIME(f(n)) For Formal System F1
426NT* : Near-Testable With Forest Ordering1
427coSL : Complement of SL1
428FPTnu : Fixed-Parameter Tractable (nonuniform)1
429compIP : Competitive IP Proof System1
430RHSPACE(f(n)) : One-Sided Error Halting Probabilistic f(n)-Space1
431FPTsu : Fixed-Parameter Tractable (strongly uniform)1
432para-NL[f log] : Parameterized Nondeterministic Logspace1
433AW[P] : Alternating W[P]1
434LogFew : Logspace-Bounded Few1
435Dyn-FO : Dynamic FO1
436ZPPcc : Communication Complexity ZPP1
437F-TAPE(f(n)) : Provable DSPACE(f(n)) For Formal System F1
438AW[t] : Alternating W[t]1
439HeurBPP : Heuristic BPP1
440LogFewNL : Logspace-Bounded FewP1
441RNC1 : Randomized NC11
442IPP : Unbounded IP1
443PostBPP : BPP With Postselection1
444PSPACE/poly : PSPACE With Polynomial-Size Advice1
445PL1 : Polynomially-Bounded L1 Spectral Norm1
446EEE : Triple-Exponential Time With Linear Exponent1
447PT/WK(f(n),g(n)) : Parallel Time f(n) / Work g(n)1
448S : Exclusive Stochastic Languages1
449NLIN : Nondeterministic LIN1
450QNC0/🐱 : Quantum NC0 With Polynomial-Size Quantum Advice1
451Dyn-ThC0 : Dynamic Threshold Circuits1
452SO[TC] : Second-Order logic with transitive closure1
453FPRAS : Fully Polynomial Randomized Approximation Scheme1