Complexity Zoo

Welcome to a modified version of Complexity Zoo.

There are now 603 classes.

Created by Satoshi Hada. I will welcome any comment.

Last Updated: 2025-05-04 07:38:03 +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 description has a link to the class.

Rank	Class	Description	Score
1	P	Polynomial-Time	143
2	NP	Nondeterministic Polynomial-Time	135
3	BPP	Bounded-Error Probabilistic Polynomial-Time	63
4	PSPACE	Polynomial-Space	54
5	PH	Polynomial-Time Hierarchy	45
6	P/poly	Nonuniform Polynomial-Time	42
7	BQP	Bounded-Error Quantum Polynomial-Time	40
8	EXP	Exponential Time	38
9	PP	Probabilistic Polynomial-Time	36
10	L	Logarithmic Space	33
11	NL	Nondeterministic Logarithmic-Space	27
12	MA	Merlin-Arthur	24
13	NEXP	Nondeterministic EXP	24
14	#P	Sharp-P or Number-P	22
15	QMA	Quantum MA	20
16	AM	Arthur-Merlin	19
17	coNP	Complement of NP	19
18	DTIME(f(n))	Deterministic f(n)-Time	19
19	E	Exponential Time With Linear Exponent	18
20	FP	Function Polynomial-Time	17
21	IP	Interactive Proof Systems	17
22	RP	Randomized Polynomial-Time	17
23	SZK	Statistical Zero Knowledge	17
24	AC0	Unbounded Fanin Constant-Depth Circuits	16
25	NC	Nick's Class	15
26	NC1	Level 1 of NC	15
27	ZPP	Zero-Error Probabilistic Polynomial-Time	15
28	DSPACE(f(n))	Deterministic f(n)-Space	14
29	FPT	Fixed-Parameter Tractable	14
30	UP	Unambiguous Polynomial-Time	13
31	NE	Nondeterministic E	12
32	Σ2P	NP With NP Oracle	12
33	FO	First-Order logic	11
34	ModkP	Mod-k Polynomial-Time	11
35	EQP	Exact Quantum Polynomial-Time	10
36	MIP	Multi-Prover Interactive Proof	10
37	FNP	Function NP	9
38	NP ∩ coNP	The intersection of NP and coNP	9
39	⊕P	Parity P	9
40	TC0	Constant-Depth Threshold Circuits	9
41	BQP/mpoly	BQP With Polynomial-Size Deterministic Merlin-Like Advice	8
42	C=P	Exact-Counting Polynomial-Time	8
43	NEE	Nondeterministic EE	8
44	NP/poly	Nonuniform NP	8
45	NTIME(f(n))	Nondeterministic f(n)-Time	8
46	Pcc	Communication Complexity P	8
47	PNP[log]	P With Log NP Queries	8
48	Δ2P	P With NP Oracle	7
49	DET	Determinant	7
50	EE	Double-Exponential Time With Linear Exponent	7
51	NPcc	Communication Complexity NP	7
52	k-PBP	Polynomial-Size Width-k Branching Program	7
53	PPA	Polynomial Parity Argument	7
54	PPcc	Communication Complexity PP	7
55	PTAS	Polynomial-Time Approximation Scheme	7
56	QIP	Quantum IP	7
57	RE	Recursively Enumerable Languages	7
58	S2P	Second Level of the Symmetric Hierarchy	7
59	AC	Unbounded Fanin Polylogarithmic-Depth Circuits	6
60	AC1	Unbounded Fanin Log-Depth Circuits	6
61	AWPP	Almost WPP	6
62	BPEE	Bounded-Error Probabilistic EE	6
63	BPL	Bounded-Error Probabilistic L	6
64	BQP/qpoly	BQP With Polynomial-Size Quantum Advice	6
65	coNEXP	Complement of NEXP	6
66	LOGCFL	Logarithmically Reducible to CFL	6
67	mP	Monotone P	6
68	NC2	Level 2 of NC	6
69	NPC	NP-Complete	6
70	NPO	NP Optimization	6
71	Π2P	coNP With NP Oracle	6
72	R	Recursive Languages	6
73	SBP	Small Bounded-Error Probability	6
74	SNP	Strict NP	6
75	SO	Second-Order logic	6
76	TFNP	Total Function NP	6
77	W[1]	Weighted Analogue of NP	6
78	W[t]	Nondeterministic Fixed-Parameter Hierarchy	6
79	AP	Alternating P	5
80	APX	Approximable	5
81	BPPcc	Communication Complexity BPP	5
82	BPPpath	Threshold BPP	5
83	CH	Counting Hierarchy	5
84	coAM	Complement of AM	5
85	coNE	Complement of NE	5
86	coNPcc	Complement of NPcc	5
87	EH	Exponential-Time Hierarchy With Linear Exponent	5
88	FewP	NP With Few Witnesses	5
89	LWPP	Length-Dependent Wide PP	5
90	mNL	Monotone NL	5
91	ModkL	Mod-k L	5
92	NC0	Level 0 of NC	5
93	NQP	Nondeterministic Quantum Polynomial-Time	5
94	PC	Polynomial-Time Over The Complex Numbers	5
95	PPAD	Polynomial Parity Argument (Directed)	5
96	PPP	Polynomial Pigeonhole Principle	5
97	PR	Polynomial-Time Over The Reals	5
98	PZK	Perfect Zero Knowledge	5
99	QSZK	Quantum Statistical Zero-Knowledge	5
100	RNC	Randomized NC	5
101	SL	Symmetric Logarithmic-Space	5
102	SPP	Stoic PP	5
103	UPPcc	Unrestricted Communication Analogue of PP	5
104	VPk	Valiant P Over Field k	5
105	ACC0	AC0 With Arbitrary MOD Gates	4
106	AM[polylog]	AM With Polylog Rounds	4
107	APP	Amplified PP	4
108	BP•L	Bounded-Error Probabilistic L with Two Way Access to Randomness	4
109	CFL	Context-Free Languages	4
110	CZK	Computational Zero-Knowledge	4
111	FO[${\displaystyle t(n)}$]	Iterated First-Order logic	4
112	frIP	Function-Restricted IP Proof Systems	4
113	GapL	Gap Logarithmic-Space	4
114	MaxSNP	Maximization SNP	4
115	mL	Monotone L	4
116	mNC1	Monotone NC1	4
117	NISZK	Non-Interactive SZK	4
118	NPC	NP Over The Complex Numbers	4
119	NSPACE(f(n))	Nondeterministic f(n)-Space	4
120	O2P	Second Level of the Oblivious Symmetric Hierarchy	4
121	PBP	Polynomial-Size Branching Program	4
122	PHcc	Communication Complexity PH	4
123	PLS	Polynomial Local Search	4
124	P-OBDD	Polynomial-Size Ordered Binary Decision Diagram	4
125	PostBQP	BQP With Postselection	4
126	PR	Primitive Recursive Functions	4
127	P-Sel	P-Selective Sets	4
128	P#P	P With #P Oracle	4
129	QIP[2]	2-Message Quantum IP	4
130	QNC	Quantum NC	4
131	QP	Quasipolynomial-Time	4
132	RG(2)	Two-turn (one-round) Refereed Games	4
133	RL	Randomized Logarithmic-Space	4
134	SC	Steve's Class	4
135	#L	Sharp-L	4
136	W[P]	Weighted Circuit Satisfiability	4
137	WPP	Wide PP	4
138	W[SAT]	Weighted Satisfiability	4
139	XP	Fixed-Parameter Tractable for Each Parameter	4
140	YP	Your Polynomial-Time or Yaroslav-Percival	4
141	AC0[m]	AC0 With MOD m Gates	3
142	AMcc	Communication Complexity AM	3
143	AmpMP	Amplifiable MP	3
144	AvgP	Average Polynomial-Time	3
145	BH	Boolean Hierarchy Over NP	3
146	BPP/mlog	BPP With Logarithmic Deterministic Merlin-Like Advice	3
147	BPSPACE(f(n))	Bounded-Error Probabilistic f(n)-Space	3
148	BPTIME(f(n))	Bounded-Error Probabilistic f(n)-Time	3
149	BQP/poly	BQP With Polynomial-Size Karp-Lipton Advice	3
150	coC=P	Complement of C=P	3
151	coRE	Complement of RE	3
152	coRP	Complement of RP	3
153	DCFL	Deterministic CFL	3
154	DiffAC0	Difference #AC0	3
155	DistNP	Distributional NP	3
156	EEXP	Double-Exponential Time	3
157	ELEMENTARY	Finitely Iterated Exponential Time	3
158	EXPSPACE	Exponential Space	3
159	FBQP	Function BQP	3
160	FNL	Function NL	3
161	FO(TC)	First-order with transitive closure	3
162	FPTAS	Fully Polynomial-Time Approximation Scheme	3
163	GapP	Gap Polynomial-Time	3
164	L/poly	Nonuniform Logarithmic Space	3
165	MAEXP	Exponential-Time MA	3
166	MaxPB	MaxNP Polynomially Bounded	3
167	mcoNL	Complement of mNL	3
168	MIP*	MIP With Quantum Provers	3
169	ModPH	Modular Counting Hierarchy	3
170	MP	Middle-Bit P	3
171	NEEXP	Nondeterministic EEXP	3
172	NPMV	NP Multiple Value	3
173	NPMVt	NPMV Total	3
174	NPR	NP Over The Reals	3
175	NPSV	NP Single Value	3
176	NQL	Nondet Quasi-Linear	3
177	ONP	Oblivious NP	3
178	para-	Parameterized Complexity	3
179	P${\displaystyle k}$cc	Pcc in NOF model, ${\displaystyle k}$ players	3
180	PL	Probabilistic L	3
181	PNP	P With Oracle Access To NP	3
182	PostBPPcc	Communication Complexity PostBPP	3
183	PPADS	Polynomial Parity Argument (Directed, Sink)	3
184	P||NP	P With Parallel Queries To NP	3
185	PPSPACE	Probabilistic PSPACE	3
186	PromiseBPP	Promise-Problem BPP	3
187	QAC0[m]	Quantum AC0[m]	3
188	QACC0	Quantum ACC0	3
189	QMA(2)	Quantum MA With Multiple Certificates	3
190	QMIP	Quantum Multi-Prover Interactive Proofs	3
191	QNC0	Quantum NC0	3
192	QRG(2)	Two-turn (one-round) Quantum Refereed Games	3
193	QRG(k)	k-turn Quantum Refereed Games	3
194	RG	Refereed Games	3
195	RG(k)	k-turn Refereed Games	3
196	S2-EXP•PNP	Don't Ask	3
197	SPARSE	Sparse Languages	3
198	SQG	Short Quantum Games	3
199	⊕L	Parity L	3
200	TALLY	Tally Languages	3
201	UL	Unambiguous L	3
202	VNPk	Valiant NP Over Field k	3
203	WAPP	Weak Almost-Wide PP	3
204	XL	Fixed-Parameter Logspace for Each Parameter	3
205	XPuniform	Uniform XP	3
206	YQP*	Yaroslav BQP star	3
207	ZBQP	Strict Quantum ZPP	3
208	A0PP	One-Sided Analog of AWPP	2
209	AL	Alternating L	2
210	ALL	The Class of All Languages	2
211	Almost-P	Languages Almost Surely in PA	2
212	AW[SAT]	Alternating W[SAT]	2
213	AW[*]	Alternating W[*]	2
214	AxP	Approximable in Polynomial Time	2
215	βP	Limited-Nondeterminism NP	2
216	BPd(P)	Polynomial Size d-Times-Only Branching Program	2
217	BPE	Bounded-Error Probabilistic E	2
218	BPHSPACE(f(n))	Bounded-Error Halting Probabilistic f(n)-Space	2
219	BPP${\displaystyle k}$cc	BPPcc in NOF model, ${\displaystyle k}$ players	2
220	BPP-OBDD	Polynomial-Size Bounded-Error Ordered Binary Decision Diagram	2
221	BPP/rlog	BPP With Logarithmic Probabilistically Sampled Random Advice	2
222	BQP/mlog	BQP With Logarithmic-Size Deterministic Merlin-Like Advice	2
223	BQP/qlog	BQP With Logarithmic-Size Quantum Advice	2
224	Check	Checkable Languages	2
225	Coh	Coherent Languages	2
226	compNP	Competitive NP Proof System	2
227	coNL	Complement of NL	2
228	coUP	Complement of UP	2
229	CP	Continuous P	2
230	DQP	Dynamical Quantum Polynomial-Time	2
231	k-EQBP	Width-k Polynomial-Time Exact Quantum Branching Programs	2
232	ESPACE	Exponential Space With Linear Exponent	2
233	∃BPP	BPP With Existential Operator	2
234	Few	FewP With Flexible Acceptance Mechanism	2
235	FO(LFP)	First-order with least fixed point	2
236	FOLL	First-Order log log n	2
237	FO(PFP)	First-order with partial fixed point	2
238	GA	Graph Automorphism	2
239	GapAC0	Gap #AC0	2
240	GI	Graph Isomorphism	2
241	GPCD(r(n),q(n))	Generalized Probabilistically Checkable Debate	2
242	HeurDTIME${\displaystyle \mathrm{\delta <!--\; \delta \; -->}}$(f(n))	Heuristic DTIME	2
243	IC[log,poly]	Logarithmic Instance Complexity, Polynomial Time	2
244	LkP	Low Hierarchy In NP	2
245	LOGNP	Logarithmically-Restricted NP	2
246	LOGSNP	Logarithmically-Restricted SNP	2
247	MAC0	Majority of AC0	2
248	MAE	Exponential-Time MA With Linear Exponent	2
249	MaxNP	Maximization NP	2
250	MMSNP	Monadic Monotone SNP	2
251	mNP	Monotone NP	2
252	NAuxPDAp	Nondeterministic Auxiliary Pushdown Automata	2
253	NEXP/poly	Nonuniform NEXP	2
254	NL/poly	Nonuniform NL	2
255	NPI	NP-Intermediate	2
256	NP${\displaystyle k}$cc	NPcc in NOF model, ${\displaystyle k}$ players	2
257	NPOPB	NPO Polynomially Bounded	2
258	(NP,P-samplable)	Average NP With Samplable Distributions	2
259	NPSPACE	Nondeterministic PSPACE	2
260	NPSVt	NPSV Total	2
261	PCD(r(n),q(n))	Probabilistically Checkable Debate	2
262	PCP(r(n),q(n))	Probabilistically Checkable Proof	2
263	PDQP	Product Dynamical Quantum Polynomial time	2
264	P/log	P With Logarithmic Advice	2
265	PNPcc	Communication Complexity PNP	2
266	PPP	P With PP Oracle	2
267	PromiseP	Promise-Problem P	2
268	PT1	Polynomial Threshold Functions	2
269	Q	Quasi-Realtime Languages	2
270	QAC0	Quantum AC0	2
271	QACf0	QAC0 With Fanout	2
272	QL	Quasi-Linear	2
273	QMA-plus	QMA With Super-Verifier	2
274	QMA/qpoly	QMA With Polynomial-Size Quantum Advice	2
275	QMIPne	Quantum Multi-Prover Interactive Proofs With No Prior Entanglement	2
276	QNCf0	Quantum NC0 With Unbounded Fanout	2
277	QPH	Quantum PH	2
278	QRG	Quantum Refereed Games	2
279	QRG(1)	One-turn Quantum Refereed Games	2
280	QRL	Quantum Regular Languages	2
281	RBQP	Strict Quantum RP	2
282	REG	Regular Languages	2
283	RG(1)	One-turn Refereed Games	2
284	RP${\displaystyle k}$cc	Randomized P${\displaystyle k}$cc	2
285	RQP	One-sided Error Extension of EQP	2
286	SAC	Semi-Unbounded-Fanin AC	2
287	SAC1	Semi-Unbounded-Fanin AC1	2
288	SAPTIME	Stochastic Alternating Polynomial-Time	2
289	SBPcc	Communication Complexity SBP	2
290	⊕Pcc	Communication Complexity ⊕P	2
291	#AC0	Sharp-AC0	2
292	TC	Threshold Circuits	2
293	TOWER	Iterated Exponential Time	2
294	UCFL	Unambiguous CFL	2
295	UL/poly	Nonuniform UL	2
296	XNL	Fixed-Parameter Nondeterministic Logspace for Each Parameter	2
297	YP*	Yaroslav-Percival Star	2
298	YPP	Yaroslav BPP	2
299	YQP	Yaroslav BQP	2
300	ZK	Zero-Knowledge (see CZK)	2
301	ZP•L	Zero-Error Probabilistic L with Two Way Access to Randomness	2
302	ZQP	Zero-Error Extension Of EQP	2
303	AH	Arithmetic Hierarchy	1
304	ALOGTIME	Logarithmic time alternating RAM	1
305	AMEXP	Exponential-Time AM	1
306	AUC-SPACE(f(n))	Randomized Alternating f(n)-Space	1
307	AVBPP	Average-Case BPP	1
308	AW[P]	Alternating W[P]	1
309	AW[t]	Alternating W[t]	1
310	AxPP	Approximable in Probabilistic Polynomial Time	1
311	BPPKT	BPP With Time-Bounded Kolmogorov Complexity Oracle	1
312	BPP/log	BPP With Logarithmic Karp-Lipton Advice	1
313	BPP//log	BPP With Logarithmic Randomness-Dependent Advice	1
314	BPQP	Bounded-Error Probabilistic QP	1
315	BQP/log	BQP With Logarithmic-Size Karp-Lipton Advice	1
316	BQP-OBDD	Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram	1
317	BQTIME(f(n))	Bounded-Error Quantum f(n)-Time	1
318	CC0	Constant-Depth MODm Circuits	1
319	C=AC0	Exact-Counting AC0	1
320	C=L	Exact-Counting L	1
321	CkP	kth Level of CH	1
322	CL	Catalytic Logspace	1
323	CLOG	Continuous Logarithmic-Time	1
324	CNP	Continuous NP	1
325	cofrIP	Complement of frIP	1
326	compIP	Competitive IP Proof System	1
327	coNQP	Complement of NQP	1
328	coRNC	Complement of RNC	1
329	coSL	Complement of SL	1
330	coSPARSE	Complement of SPARSE	1
331	CSIZE(f(n))	Circuit Size f(n)	1
332	CSL	Context Sensitive Languages	1
333	CSP	Constraint Satisfaction Problems	1
334	CSPACE	Catalytic space	1
335	δ-BPP	δ-Semi-Random BPP	1
336	DP or Dp	Difference Polynomial-Time	1
337	DTISP(t(n),s(n))	Simultaneous t(n)-Time and s(n)-Space	1
338	Dyn-FO	Dynamic FO	1
339	Dyn-ThC0	Dynamic Threshold Circuits	1
340	EEE	Triple-Exponential Time With Linear Exponent	1
341	EESPACE	Double-Exponential Space With Linear Exponent	1
342	EP	NP with 2k Accepting Paths	1
343	EPTAS	Efficient Polynomial-Time Approximation Scheme	1
344	EQPK	Exact Quantum Polynomial-Time with Gate Set K	1
345	FERT	Fixed Error Randomized Time	1
346	FO(DTC)	First-order with deterministic transitive closure	1
347	FPERT	Fixed Parameter and Error Randomized Time	1
348	FPR	Fixed-Parameter Randomized	1
349	FPRAS	Fully Polynomial Randomized Approximation Scheme	1
350	FPTnu	Fixed-Parameter Tractable (nonuniform)	1
351	FPTsu	Fixed-Parameter Tractable (strongly uniform)	1
352	F-TAPE(f(n))	Provable DSPACE(f(n)) For Formal System F	1
353	F-TIME(f(n))	Provable DTIME(f(n)) For Formal System F	1
354	GAN-SPACE(f(n))	Games Against Nature f(n)-Space	1
355	GCSL	Growing CSL	1
356	HeurBPP	Heuristic BPP	1
357	HeurBPTIME(f(n))	Heuristic BPTIME(f(n))	1
358	HeurP	Heuristic P	1
359	HkP	High Hierarchy In NP	1
360	HVPZK	Honest-Verifier PZK	1
361	HVSZK	Honest-Verifier SZK	1
362	IPP	Unbounded IP	1
363	LC0	Unbounded Fanin Linear Size (gates) Constant-Depth Circuits	1
364	LIN	Linear Time	1
365	LogFew	Logspace-Bounded Few	1
366	LogFewNL	Logspace-Bounded FewP	1
367	MAcc	Communication Complexity MA	1
368	mAL	Monotone AL	1
369	MAPOLYLOG	MA With Polylog Verifier	1
370	MaxSNP0	Generating Class of MaxSNP	1
371	MinPB	MinNP Polynomially Bounded	1
372	MIPEXP	Exponential-Time Multi-Prover Interactive Proof	1
373	ModP	ModkP With Arbitrary k	1
374	ModZkL	Restricted ModkL	1
375	mP/poly	Monotone P/poly	1
376	mTC0	Monotone TC0	1
377	NE/poly	Nonuniform NE	1
378	NIPZK	Non-Interactive PZK	1
379	NISZKh	NISZK With Limited Help	1
380	NLIN	Nondeterministic LIN	1
381	NLT	Nearly Linear Time	1
382	NNLT	Nondeterministic Nearly Linear Time	1
383	NT	Near-Testable	1
384	NT*	Near-Testable With Forest Ordering	1
385	OMA	Oblivious MA	1
386	OptP	Optimum Polynomial-Time	1
387	PAC0	Probabilistic AC0	1
388	para-NL	Parameterized Nondeterministic Logspace	1
389	para-NL[f log]	Parameterized Nondeterministic Logspace	1
390	PermUP	Self-Permuting UP	1
391	PINC	Polynomial Ignorance of Names of Classes	1
392	PIO	Polynomial Input Output	1
393	PK	P With Kolmogorov-Complexity Oracle	1
394	PKC	Perfect Knowledge Complexity	1
395	PL1	Polynomially-Bounded L1 Spectral Norm	1
396	PL∞	Polynomially-Bounded L∞-1 Spectral Norm	1
397	P-LOCAL	Polylogarithmic rounds in the LOCAL model	1
398	PNP[k]	P With k NP Queries(for constant k)	1
399	polyL	Polylogarithmic Space	1
400	PostBPP	BPP With Postselection	1
401	P||QMA	P With Parallel Queries To QMA	1
402	PQMA[log]	P With Log QMA Queries	1
403	PrHSPACE(f(n))	Unbounded-Error Halting Probabilistic f(n)-Space	1
404	P-RLOCAL	Polylogarithmic rounds in the Randomized LOCAL model	1
405	PromiseRP	Promise-Problem RP	1
406	PromiseUP	Promise-Problem UP	1
407	PrSPACE(f(n))	Unbounded-Error Probabilistic f(n)-Space	1
408	P#P[1]	P With Single Query To #P Oracle	1
409	PSPACE/poly	PSPACE With Polynomial-Size Advice	1
410	PT/WK(f(n),g(n))	Parallel Time f(n) / Work g(n)	1
411	QCFL	Quantum CFL	1
412	QCMA	Quantum Classical MA	1
413	QCPH	Quantum Classical PH	1
414	QH	Query Hierarchy Over NP	1
415	QMA+	QMA With Non-Negative Amplitudes	1
416	QMAlog	QMA With Logarithmic-Size Proofs	1
417	QMIPle	Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement	1
418	QNC0/🐱	Quantum NC0 With Polynomial-Size Quantum Advice	1
419	QNC0/qpoly	Quantum NC0 With Polynomial-Size Quantum Advice	1
420	QPLIN	Linear Quasipolynomial-Time	1
421	RevSPACE(f(n))	Reversible f(n)-Space	1
422	RHL	Randomized Halting Logarithmic-Space	1
423	RHSPACE(f(n))	One-Sided Error Halting Probabilistic f(n)-Space	1
424	RNC1	Randomized NC1	1
425	RSPACE(f(n))	Randomized f(n)-Space	1
426	SBQP	Small Bounded-Error Quantum Polynomial-Time	1
427	SEH	Strong Exponential Hierarchy	1
428	SelfNP	Self-Witnessing NP	1
429	SIZE(f(n))	Circuit Size f(n)	1
430	S≠	Exclusive Stochastic Languages	1
431	SO(Krom)	Second-order in Krom form	1
432	SO[LFP]	Second-Order logic with least fixed point	1
433	SO[TC]	Second-Order logic with transitive closure	1
434	SZKh	SZK With Limited Help	1
435	2-EXP	Double-Exponential Time	1
436	⊕SAC1	AC1 With Unbounded Parity Gates	1
437	#L/poly	Nonuniform #L	1
438	TC1	Log-depth Threshold Circuits	1
439	Θ2P	Alternate name for PNP[log]	1
440	TreeBQP	BQP Restricted To Tree States	1
441	UCC	Unique Connected Component	1
442	UE	Unambiguous Exponential-Time With Linear Exponent	1
443	UPcc	Communication Complexity UP	1
444	UPostBPPcc	Unrestricted Communication Analogue of PostBPP	1
445	VCk	Verification Class With A Circuit of Depth K	1
446	VNCk	Valiant NC Over Field k	1
447	VQPk	Valiant QP Over Field k	1
448	WAPPcc	Communication Complexity WAPP	1
449	WHILE	While programs and some restrictions	1
450	WLC0	Unbounded Fanin Linear Size (wires) Constant-Depth Circuits	1
451	W[*]	Union of W[t]'s	1
452	W*[t]	W[t] With Parameter-Dependent Depth	1
453	XOR-MIP*[2,1]	MIP*[2,1] With 1-Bit Proofs	1
454	ZPPcc	Communication Complexity ZPP	1
455	0-1-NPC	Binary Restriction of NP Over The Complex Numbers	0
456	1NAuxPDAp	One-Way NAuxPDAp	0
457	3SUM-hard	Problems hard for 3SUM	0
458	#GA	Graph Automorphism	0
459	#W[t]	Sharp-W[t]	0
460	⊕EXP	Parity EXP	0
461	⊕L/poly	Nonuniform ⊕L	0
462	⊕SAC0	AC0 With Unbounded Parity Gates	0
463	Ack	Ackermann Time	0
464	AlgP/poly	Polynomial-Size Algebraic Circuits	0
465	Almost-NP	Languages Almost Surely in NPA	0
466	Almost-PSPACE	Languages Almost Surely in PSPACEA	0
467	AM ∩ coAM	The intersection of AM and coAM	0
468	AmpP-BQP	BQP Restricted To AmpP States	0
469	APSPACE	Alternating PSPACE	0
470	AuxPDA	Auxiliary Pushdown Automata	0
471	AvgE	Average Exponential-Time With Linear Exponent	0
472	βFOLL	Limited-Nondeterminism FOLL	0
473	βMAC0	Limited-Nondeterminism MAC0	0
474	BC=P	Bounded-Error C=P	0
475	BP•NP	Probabilistic NP	0
476	BQL	Bounded-Error Quantum Logspace	0
477	BQNC	Alternate Name for QNC	0
478	BQNP	Alternate Name for QMA	0
479	BQPSPACE	Bounded-Error Quantum PSPACE	0
480	BQPtt/poly	BQP/mpoly With Truth-Table Queries	0
481	k-BWBP	Bounded-Width Branching Program	0
482	CC	Comparator Circuits	0
483	CL#P	Cluster Sharp-P	0
484	coMA	Complement of MA	0
485	coModkP	Complement of ModkP	0
486	coNPC	coNP-Complete	0
487	coNP/poly	Complement of NP/poly	0
488	coUCC	Complement of UCC	0
489	cq-Σ2	Classical-Quantum-Σ2P	0
490	D#P	Alternate Name for P#P	0
491	δ-RP	δ-Semi-Random RP	0
492	DistributionPH	Distribution PH	0
493	DisNP	Disjoint NP Pairs	0
494	DQC1	Deterministic Quantum Computing with 1 Clean Bit	0
495	ELkP	Extended Low Hierarchy	0
496	EQTIME(f(n))	Exact Quantum f(n)-Time	0
497	∃NISZK	NISZK With Existential Operator	0
498	∃R	Existential theory of the reals	0
499	EXP/poly	Exponential Time With Polynomial-Size Advice	0
500	FBPP	Function BPP	0
501	FewEXP	NEXP With Few Witnesses	0
502	FH	Fourier Hierarchy	0
503	FIXP	Fixed Point	0
504	FNL/poly	Nonuniform FNL	0
505	FPNP[log]	FP With Logarithmically Many Queries To NP	0
506	FPL	Fixed Parameter Linear	0
507	FQMA	Function QMA	0
508	GC(s(n),C)	Guess and Check	0
509	GLO	Guaranteed Local Optima	0
510	G[t]	Stratification of Fixed-Parameter Tractable Problems	0
511	HalfP	RP With Exactly Half Acceptance	0
512	HeurPP	Heuristic PP	0
513	HeurNTIME${\displaystyle \mathrm{\delta <!--\; \delta \; -->}}$(f(n))	Heuristic NTIME	0
514	HO	High-Order logic	0
515	IOP	Interactive Oracle Proof	0
516	IP[polylog]	IP With Polylog Rounds	0
517	K	Feasibly recursive functions	0
518	LH	Logarithmic Time Hierarchy	0
519	LOGLOG	loglog Space	0
520	MA'	Sparse MA	0
521	MIPns	MIP with Non-Signaling Provers	0
522	(Mk)P	Acceptance Mechanism by Monoid Mk	0
523	MM	Problems reducible to matrix multiplication	0
524	ModL	ModL	0
525	MPC	Monotone Planar Circuits	0
526	naCQP	non-adaptive Collapse-free Quantum Polynomial time	0
527	Nearly-P	Languages Superpolynomially Close to P	0
528	NEEE	Nondeterministic EEE	0
529	NIQSZK	Non-Interactive QSZK	0
530	NLO	NL Optimization Problems	0
531	NLOG	NL With Nondeterministic Oracle Tape	0
532	NMCL	Nondeterministic Moore-Crutchfield Languages	0
533	NONE	The Empty Class	0
534	(NP ∩ coNP)/poly	Nonuniform NP ∩ coNP	0
535	NP/log	NP With Logarithmic Advice	0
536	NPMV-sel	NPMV Selective	0
537	NPMVt-sel	NPMVt Selective	0
538	NPSV-sel	NPSV Selective	0
539	NPSVt-sel	NPSVt Selective	0
540	NQL	Nondeterministic Quantum Languages	0
541	OIP	Oblivious IP	0
542	PCTC	P With Closed Time Curves	0
543	para-L	Parameterized Logspace	0
544	para-P	Parameterized Polynomial time.	0
545	P-Close	Problems Close to P	0
546	PEXP	Probabilistic Exponential-Time	0
547	PF	Alternate Name for FP	0
548	PFCHK(t(n))	Proof-Checker	0
549	Φ2P	Second Level of the Symmetric Hierarchy, Alternative Definition	0
550	PhP	Physical Polynomial-Time	0
551	PLF	Polynomial Leaf	0
552	PLL	Polynomial Local Lemma	0
553	PNP[log^2]	P With Log2 NP Queries	0
554	PODN	Polynomial Odd Degree Node	0
555	PP/poly	Nonuniform PP	0
556	PQP	Probabilistic Quantum Polynomial-Time	0
557	PQUERY	PSPACE With Polynomial Queries	0
558	PromiseBQP	Promise-Problem BQP	0
559	PSK	Polynomial Sink	0
560	PSPACEcc	Communication Complexity PSPACE	0
561	PTAPE	Archaic for PSPACE	0
562	PureSuperQMA	A pure-state analog of SuperQMA	0
563	QAM	Quantum AM	0
564	QEPH	Entangled Quantum PH	0
565	QMA1	One Sided QMA	0
566	QMA+(2)	QMA(2) With Non-Negative Amplitudes	0
567	QMAM	Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs	0
568	QNC1	Quantum NC1	0
569	QPIP	Quantum Prover Interactive Proof	0
570	QPSPACE	Quasipolynomial-Space	0
571	RPcc	Communication Complexity RP	0
572	RPP	Restricted Pseudo Polynomial-Time	0
573	S2E	Second Level of the Symmetric Linear Exponent Hierarchy	0
574	SAC0	Semi-Unbounded-Fanin AC0	0
575	SE	Subexponentially-Solvable Search Problems	0
576	SFk	Width-k Bottleneck Turing Machines	0
577	SKC	Statistical Knowledge Complexity	0
578	SLICEWISE PSPACE	Parametrized PSPACE	0
579	SO(Horn)	Second-order in Horn form	0
580	SO[${\displaystyle t(n)}$]	Iterated Second-Order logic	0
581	SP	Semi-Efficient Parallel	0
582	span-L	Span Logarithmic-Space	0
583	span-P	Span Polynomial-Time	0
584	SPL	Stoic PL	0
585	StoqMA	Stoquastic MA	0
586	SUBEXP	Deterministic Subexponential-Time	0
587	symP	Alternate Name for S2P	0
588	TC0(FOLL)	Languages that are TC0 Turing reducible to FOLL	0
589	TI	Tensor Isomorphism	0
590	TREE-REGULAR	Regular Tree-Valued Languages	0
591	UAMcc	Unambiguous Arthur-Merlin Communication Complexity	0
592	UAP	Unambiguous Alternating Polynomial-Time	0
593	US	Unique Polynomial-Time	0
594	USBPcc	Unrestricted Communication Analogue of SBP	0
595	UWAPPcc	Unrestricted Communication Analogue of WAPP	0
596	VCor	Verification Class With OR	0
597	VPL	Visibly pushdown languages	0
598	XNLP	Fixed-Parameter Nondeterministic Logspace and Polytime for Each Parameter	0
599	YACC	Yet Another Complexity Class	0
600	YQP*/poly	YQP* With Polynomial-Size Advice	0
601	ZAMcc	Zero-Information Arthur-Merlin Communication Complexity	0
602	ZPE	Zero-Error Probabilistic E	0
603	ZPTIME(f(n))	Zero-Error Probabilistic f(n)-Time	0