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.
Rank | Class | 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 | NEXP : Nondeterministic EXP | 24 |
13 | MA : Merlin-Arthur | 23 |
14 | #P : Sharp-P or Number-P | 22 |
15 | QMA : Quantum MA | 20 |
16 | DTIME(f(n)) : Deterministic f(n)-Time | 19 |
17 | AM : Arthur-Merlin | 19 |
18 | coNP : Complement of NP | 19 |
19 | E : Exponential Time With Linear Exponent | 18 |
20 | FP : Function Polynomial-Time | 17 |
21 | SZK : Statistical Zero Knowledge | 17 |
22 | RP : Randomized Polynomial-Time | 17 |
23 | IP : Interactive Proof Systems | 16 |
24 | AC0 : Unbounded Fanin Constant-Depth Circuits | 16 |
25 | NC1 : Level 1 of NC | 15 |
26 | NC : Nick's Class | 15 |
27 | ZPP : Zero-Error Probabilistic Polynomial-Time | 15 |
28 | FPT : Fixed-Parameter Tractable | 14 |
29 | DSPACE(f(n)) : Deterministic f(n)-Space | 14 |
30 | UP : Unambiguous Polynomial-Time | 13 |
31 | Σ2P : NP With NP Oracle | 12 |
32 | NE : Nondeterministic E | 11 |
33 | ModkP : Mod-k Polynomial-Time | 11 |
34 | FO : First-Order logic | 11 |
35 | EQP : Exact Quantum Polynomial-Time | 10 |
36 | NP ∩ coNP : | 9 |
37 | FNP : Function NP | 9 |
38 | TC0 : Constant-Depth Threshold Circuits | 9 |
39 | MIP : Multi-Prover Interactive Proof | 9 |
40 | ⊕P : Parity P | 9 |
41 | Pcc : Communication Complexity P | 8 |
42 | C=P : Exact-Counting Polynomial-Time | 8 |
43 | NTIME(f(n)) : Nondeterministic f(n)-Time | 8 |
44 | BQP/mpoly : BQP With Polynomial-Size Deterministic Merlin-Like Advice | 8 |
45 | PNP[log] : P With Log NP Queries | 8 |
46 | NEE : Nondeterministic EE | 8 |
47 | NP/poly : Nonuniform NP | 8 |
48 | DET : Determinant | 7 |
49 | EE : Double-Exponential Time With Linear Exponent | 7 |
50 | NPcc : Communication Complexity NP | 7 |
51 | PPcc : Communication Complexity PP | 7 |
52 | S2P : Second Level of the Symmetric Hierarchy | 7 |
53 | PTAS : Polynomial-Time Approximation Scheme | 7 |
54 | k-PBP : Polynomial-Size Width-k Branching Program | 7 |
55 | Δ2P : P With NP Oracle | 7 |
56 | RE : Recursively Enumerable Languages | 7 |
57 | PPA : Polynomial Parity Argument | 7 |
58 | QIP : Quantum IP | 7 |
59 | SO : Second-Order logic | 6 |
60 | NC2 : Level 2 of NC | 6 |
61 | Π2P : coNP With NP Oracle | 6 |
62 | coNEXP : Complement of NEXP | 6 |
63 | NPC : NP-Complete | 6 |
64 | NPO : NP Optimization | 6 |
65 | SNP : Strict NP | 6 |
66 | BQP/qpoly : BQP With Polynomial-Size Quantum Advice | 6 |
67 | BPEE : Bounded-Error Probabilistic EE | 6 |
68 | TFNP : Total Function NP | 6 |
69 | W[1] : Weighted Analogue of NP | 6 |
70 | AWPP : Almost WPP | 6 |
71 | AC : Unbounded Fanin Polylogarithmic-Depth Circuits | 6 |
72 | SBP : Small Bounded-Error Probability | 6 |
73 | AC1 : Unbounded Fanin Log-Depth Circuits | 6 |
74 | W[t] : Nondeterministic Fixed-Parameter Hierarchy | 6 |
75 | BPL : Bounded-Error Probabilistic L | 6 |
76 | LOGCFL : Logarithmically Reducible to CFL | 6 |
77 | mP : Monotone P | 6 |
78 | R : Recursive Languages | 6 |
79 | SL : Symmetric Logarithmic-Space | 5 |
80 | APX : Approximable | 5 |
81 | NC0 : Level 0 of NC | 5 |
82 | CH : Counting Hierarchy | 5 |
83 | QSZK : Quantum Statistical Zero-Knowledge | 5 |
84 | ModkL : Mod-k L | 5 |
85 | mNL : Monotone NL | 5 |
86 | PZK : Perfect Zero Knowledge | 5 |
87 | BPPpath : Threshold BPP | 5 |
88 | RNC : Randomized NC | 5 |
89 | NQP : Nondeterministic Quantum Polynomial-Time | 5 |
90 | FewP : NP With Few Witnesses | 5 |
91 | EH : Exponential-Time Hierarchy With Linear Exponent | 5 |
92 | PC : Polynomial-Time Over The Complex Numbers | 5 |
93 | PPAD : Polynomial Parity Argument (Directed) | 5 |
94 | SPP : Stoic PP | 5 |
95 | BPPcc : Communication Complexity BPP | 5 |
96 | VPk : Valiant P Over Field k | 5 |
97 | coNE : Complement of NE | 5 |
98 | PR : Polynomial-Time Over The Reals | 5 |
99 | LWPP : Length-Dependent Wide PP | 5 |
100 | AP : Alternating P | 5 |
101 | UPPcc : Unrestricted Communication Analogue of PP | 5 |
102 | coNPcc : Complement of NPcc | 5 |
103 | PPP : Polynomial Pigeonhole Principle | 5 |
104 | WPP : Wide PP | 4 |
105 | RG(2) : Two-turn (one-round) Refereed Games | 4 |
106 | YP : Your Polynomial-Time or Yaroslav-Percival | 4 |
107 | O2P : Second Level of the Oblivious Symmetric Hierarchy | 4 |
108 | PBP : Polynomial-Size Branching Program | 4 |
109 | FO[ ] : Iterated First-Order logic | 4 |
110 | NISZK : Non-Interactive SZK | 4 |
111 | P-OBDD : Polynomial-Size Ordered Binary Decision Diagram | 4 |
112 | QIP[2] : 2-Message Quantum IP | 4 |
113 | BP•L : Bounded-Error Probabilistic L with Two Way Access to Randomness | 4 |
114 | GapL : Gap Logarithmic-Space | 4 |
115 | NSPACE(f(n)) : Nondeterministic f(n)-Space | 4 |
116 | CFL : Context-Free Languages | 4 |
117 | PostBQP : BQP With Postselection | 4 |
118 | QNC : Quantum NC | 4 |
119 | PLS : Polynomial Local Search | 4 |
120 | coAM : Complement of AM | 4 |
121 | PR : Primitive Recursive Functions | 4 |
122 | frIP : Function-Restricted IP Proof Systems | 4 |
123 | MaxSNP : Maximization SNP | 4 |
124 | P-Sel : P-Selective Sets | 4 |
125 | QP : Quasipolynomial-Time | 4 |
126 | NPC : NP Over The Complex Numbers | 4 |
127 | W[P] : Weighted Circuit Satisfiability | 4 |
128 | mNC1 : Monotone NC1 | 4 |
129 | P#P : P With #P Oracle | 4 |
130 | W[SAT] : Weighted Satisfiability | 4 |
131 | #L : Sharp-L | 4 |
132 | RL : Randomized Logarithmic-Space | 4 |
133 | PHcc : Communication Complexity PH | 4 |
134 | AM[polylog] : AM With Polylog Rounds | 4 |
135 | mL : Monotone L | 4 |
136 | CZK : Computational Zero-Knowledge | 4 |
137 | ACC0 : AC0 With Arbitrary MOD Gates | 4 |
138 | XP : Fixed-Parameter Tractable for Each Parameter | 4 |
139 | APP : Amplified PP | 4 |
140 | SC : Steve's Class | 4 |
141 | FNL : Function NL | 3 |
142 | QMIP : Quantum Multi-Prover Interactive Proofs | 3 |
143 | NPMV : NP Multiple Value | 3 |
144 | BQP/poly : BQP With Polynomial-Size Karp-Lipton Advice | 3 |
145 | AmpMP : Amplifiable MP | 3 |
146 | PromiseBPP : Promise-Problem BPP | 3 |
147 | NPSV : NP Single Value | 3 |
148 | EXPSPACE : Exponential Space | 3 |
149 | ELEMENTARY : Finitely Iterated Exponential Time | 3 |
150 | NPR : NP Over The Reals | 3 |
151 | MIP* : MIP With Quantum Provers | 3 |
152 | ⊕L : Parity L | 3 |
153 | NEEXP : Nondeterministic EEXP | 3 |
154 | NQL : Nondet Quasi-Linear | 3 |
155 | FPTAS : Fully Polynomial-Time Approximation Scheme | 3 |
156 | FBQP : Function BQP | 3 |
157 | para- : Parameterized Complexity | 3 |
158 | EEXP : Double-Exponential Time | 3 |
159 | MAEXP : Exponential-Time MA | 3 |
160 | AvgP : Average Polynomial-Time | 3 |
161 | GapP : Gap Polynomial-Time | 3 |
162 | UL : Unambiguous L | 3 |
163 | QAC0[m] : Quantum AC0[m] | 3 |
164 | AMcc : Communication Complexity AM | 3 |
165 | L/poly : Nonuniform Logarithmic Space | 3 |
166 | QACC0 : Quantum ACC0 | 3 |
167 | PL : Probabilistic L | 3 |
168 | NPMVt : NPMV Total | 3 |
169 | RG(k) : k-turn Refereed Games | 3 |
170 | BPP/mlog : BPP With Logarithmic Deterministic Merlin-Like Advice | 3 |
171 | PostBPPcc : Communication Complexity PostBPP | 3 |
172 | DiffAC0 : Difference #AC0 | 3 |
173 | YQP* : Yaroslav BQP star | 3 |
174 | XPuniform : Uniform XP | 3 |
175 | PPADS : Polynomial Parity Argument (Directed, Sink) | 3 |
176 | coC=P : Complement of C=P | 3 |
177 | SQG : Short Quantum Games | 3 |
178 | PPSPACE : Probabilistic PSPACE | 3 |
179 | WAPP : Weak Almost-Wide PP | 3 |
180 | DistNP : Distributional NP | 3 |
181 | coRE : Complement of RE | 3 |
182 | MaxPB : MaxNP Polynomially Bounded | 3 |
183 | PNP : P With Oracle Access To NP | 3 |
184 | ZBQP : Strict Quantum ZPP | 3 |
185 | QRG(k) : k-turn Quantum Refereed Games | 3 |
186 | P cc:Pcc in NOF model, players | 3 |
187 | FO(TC) : First-order with transitive closure | 3 |
188 | RG : Refereed Games | 3 |
189 | TALLY : Tally Languages | 3 |
190 | QRG(2) : Two-turn (one-round) Quantum Refereed Games | 3 |
191 | ONP : Oblivious NP | 3 |
192 | S2-EXP•PNP : Don't Ask | 3 |
193 | SPARSE : Sparse Languages | 3 |
194 | BPTIME(f(n)) : Bounded-Error Probabilistic f(n)-Time | 3 |
195 | MP : Middle-Bit P | 3 |
196 | BH : Boolean Hierarchy Over NP | 3 |
197 | coRP : Complement of RP | 3 |
198 | QNC0 : Quantum NC0 | 3 |
199 | QMA(2) : Quantum MA With Multiple Certificates | 3 |
200 | VNPk : Valiant NP Over Field k | 3 |
201 | AC0[m] : AC0 With MOD m Gates | 3 |
202 | P||NP : P With Parallel Queries To NP | 3 |
203 | XL : Fixed-Parameter Logspace for Each Parameter | 3 |
204 | BPSPACE(f(n)) : Bounded-Error Probabilistic f(n)-Space | 3 |
205 | mcoNL : Complement of mNL | 3 |
206 | ModPH : Modular Counting Hierarchy | 3 |
207 | DCFL : Deterministic CFL | 3 |
208 | QRG : Quantum Refereed Games | 2 |
209 | #AC0 : Sharp-AC0 | 2 |
210 | RG(1) : One-turn Refereed Games | 2 |
211 | MMSNP : Monadic Monotone SNP | 2 |
212 | QRL : Quantum Regular Languages | 2 |
213 | PPP : P With PP Oracle | 2 |
214 | CP : Continuous P | 2 |
215 | QMIPne : Quantum Multi-Prover Interactive Proofs With No Prior Entanglement | 2 |
216 | BPP-OBDD : Polynomial-Size Bounded-Error Ordered Binary Decision Diagram | 2 |
217 | mNP : Monotone NP | 2 |
218 | BPP/rlog : BPP With Logarithmic Probabilistically Sampled Random Advice | 2 |
219 | ZP•L : Zero-Error Probabilistic L with Two Way Access to Randomness | 2 |
220 | QMA/qpoly : QMA With Polynomial-Size Quantum Advice | 2 |
221 | TC : Threshold Circuits | 2 |
222 | NPI : NP-Intermediate | 2 |
223 | ESPACE : Exponential Space With Linear Exponent | 2 |
224 | PCD(r(n),q(n)) : Probabilistically Checkable Debate | 2 |
225 | QACf0 : QAC0 With Fanout | 2 |
226 | LOGSNP : Logarithmically-Restricted SNP | 2 |
227 | NEXP/poly : Nonuniform NEXP | 2 |
228 | REG : Regular Languages | 2 |
229 | MAC0 : Majority of AC0 | 2 |
230 | TOWER : Iterated Exponential Time | 2 |
231 | QNCf0 : Quantum NC0 With Unbounded Fanout | 2 |
232 | QMA-plus : QMA With Super-Verifier | 2 |
233 | LOGNP : Logarithmically-Restricted NP | 2 |
234 | NL/poly : Nonuniform NL | 2 |
235 | PCP(r(n),q(n)) : Probabilistically Checkable Proof | 2 |
236 | ZK : Zero-Knowledge (see CZK) | 2 |
237 | SAPTIME : Stochastic Alternating Polynomial-Time | 2 |
238 | UCFL : Unambiguous CFL | 2 |
239 | QAC0 : Quantum AC0 | 2 |
240 | UL/poly : Nonuniform UL | 2 |
241 | PromiseP : Promise-Problem P | 2 |
242 | MAE : Exponential-Time MA With Linear Exponent | 2 |
243 | BQP/qlog : BQP With Logarithmic-Size Quantum Advice | 2 |
244 | AW[SAT] : Alternating W[SAT] | 2 |
245 | NP cc:NPcc in NOF model, players | 2 |
246 | NPSPACE : Nondeterministic PSPACE | 2 |
247 | HeurDTIME (f(n)) : Heuristic DTIME | 2 |
248 | ALL : The Class of All Languages | 2 |
249 | GPCD(r(n),q(n)) : Generalized Probabilistically Checkable Debate | 2 |
250 | AW[*] : Alternating W[*] | 2 |
251 | NPOPB : NPO Polynomially Bounded | 2 |
252 | PDQP : Product Dynamical Quantum Polynomial time | 2 |
253 | NPSVt : NPSV Total | 2 |
254 | Coh : Coherent Languages | 2 |
255 | k-EQBP : Width-k Polynomial-Time Exact Quantum Branching Programs | 2 |
256 | MaxNP : Maximization NP | 2 |
257 | Check : Checkable Languages | 2 |
258 | GapAC0 : Gap #AC0 | 2 |
259 | BPd(P) : Polynomial Size d-Times-Only Branching Program | 2 |
260 | FO(PFP) : First-order with partial fixed point | 2 |
261 | (NP,P-samplable) : Average NP With Samplable Distributions | 2 |
262 | RBQP : Strict Quantum RP | 2 |
263 | RP cc:Randomized P cc | 2 |
264 | XNL : Fixed-Parameter Nondeterministic Logspace for Each Parameter | 2 |
265 | NAuxPDAp : Nondeterministic Auxiliary Pushdown Automata | 2 |
266 | QL : Quasi-Linear | 2 |
267 | compNP : Competitive NP Proof System | 2 |
268 | IC[log,poly] : Logarithmic Instance Complexity, Polynomial Time | 2 |
269 | YP* : Yaroslav-Percival Star | 2 |
270 | AL : Alternating L | 2 |
271 | βP : Limited-Nondeterminism NP | 2 |
272 | DQP : Dynamical Quantum Polynomial-Time | 2 |
273 | ∃BPP : BPP With Existential Operator | 2 |
274 | coNL : Complement of NL | 2 |
275 | FOLL : First-Order log log n | 2 |
276 | BPE : Bounded-Error Probabilistic E | 2 |
277 | GA : Graph Automorphism | 2 |
278 | ZQP : Zero-Error Extension Of EQP | 2 |
279 | YPP : Yaroslav BPP | 2 |
280 | QPH : Quantum PH | 2 |
281 | PNPcc : Communication Complexity PNP | 2 |
282 | GI : Graph Isomorphism | 2 |
283 | QRG(1) : One-turn Quantum Refereed Games | 2 |
284 | RQP : One-sided Error Extension of EQP | 2 |
285 | SBPcc : Communication Complexity SBP | 2 |
286 | Almost-P : Languages Almost Surely in PA | 2 |
287 | LkP : Low Hierarchy In NP | 2 |
288 | FO(LFP) : First-order with least fixed point | 2 |
289 | YQP : Yaroslav BQP | 2 |
290 | BQP/mlog : BQP With Logarithmic-Size Deterministic Merlin-Like Advice | 2 |
291 | BPHSPACE(f(n)) : Bounded-Error Halting Probabilistic f(n)-Space | 2 |
292 | coUP : Complement of UP | 2 |
293 | ⊕Pcc : Communication Complexity ⊕P | 2 |
294 | Few : FewP With Flexible Acceptance Mechanism | 2 |
295 | PT1 : Polynomial Threshold Functions | 2 |
296 | BPP cc:BPPcc in NOF model, players | 2 |
297 | Q : Quasi-Realtime Languages | 2 |
298 | AxP : Approximable in Polynomial Time | 2 |
299 | A0PP : One-Sided Analog of AWPP | 2 |
300 | P/log : P With Logarithmic Advice | 2 |
301 | PNP[k] : P With k NP Queries(for constant k) | 1 |
302 | PINC : Polynomial Ignorance of Names of Classes | 1 |
303 | CSPACE : Catalytic space | 1 |
304 | MAcc : Communication Complexity MA | 1 |
305 | WLC0 : Unbounded Fanin Linear Size (wires) Constant-Depth Circuits | 1 |
306 | NNLT : Nondeterministic Nearly Linear Time | 1 |
307 | CSL : Context Sensitive Languages | 1 |
308 | polyL : Polylogarithmic Space | 1 |
309 | CkP : kth Level of CH | 1 |
310 | CL : Catalytic Logspace | 1 |
311 | PIO : Polynomial Input Output | 1 |
312 | AMEXP : Exponential-Time AM | 1 |
313 | W[*] : Union of W[t]'s | 1 |
314 | SO(Krom) : Second-order in Krom form | 1 |
315 | CSP : Constraint Satisfaction Problems | 1 |
316 | OptP : Optimum Polynomial-Time | 1 |
317 | SEH : Strong Exponential Hierarchy | 1 |
318 | XOR-MIP*[2,1] : MIP*[2,1] With 1-Bit Proofs | 1 |
319 | EESPACE : Double-Exponential Space With Linear Exponent | 1 |
320 | QPLIN : Linear Quasipolynomial-Time | 1 |
321 | NT : Near-Testable | 1 |
322 | RevSPACE(f(n)) : Reversible f(n)-Space | 1 |
323 | P#P[1] : P With Single Query To #P Oracle | 1 |
324 | BPP/log : BPP With Logarithmic Karp-Lipton Advice | 1 |
325 | W*[t] : W[t] With Parameter-Dependent Depth | 1 |
326 | mP/poly : Monotone P/poly | 1 |
327 | QCMA : Quantum Classical MA | 1 |
328 | 2-EXP : Double-Exponential Time | 1 |
329 | PKC : Perfect Knowledge Complexity | 1 |
330 | BQTIME(f(n)) : Bounded-Error Quantum f(n)-Time | 1 |
331 | C=AC0 : Exact-Counting AC0 | 1 |
332 | BPP//log : BPP With Logarithmic Randomness-Dependent Advice | 1 |
333 | QCFL : Quantum CFL | 1 |
334 | TC1 : Log-depth Threshold Circuits | 1 |
335 | ModZkL : Restricted ModkL | 1 |
336 | PrHSPACE(f(n)) : Unbounded-Error Halting Probabilistic f(n)-Space | 1 |
337 | C=L : Exact-Counting L | 1 |
338 | DP or Dp : Difference Polynomial-Time | 1 |
339 | HVPZK : Honest-Verifier PZK | 1 |
340 | MinPB : MinNP Polynomially Bounded | 1 |
341 | TreeBQP : BQP Restricted To Tree States | 1 |
342 | NISZKh : NISZK With Limited Help | 1 |
343 | HeurBPTIME(f(n)) : Heuristic BPTIME(f(n)) | 1 |
344 | VQPk : Valiant QP Over Field k | 1 |
345 | PAC0 : Probabilistic AC0 | 1 |
346 | LC0 : Unbounded Fanin Linear Size (gates) Constant-Depth Circuits | 1 |
347 | ALOGTIME : Logarithmic time alternating RAM | 1 |
348 | coSPARSE : Complement of SPARSE | 1 |
349 | GCSL : Growing CSL | 1 |
350 | FPR : Fixed-Parameter Randomized | 1 |
351 | HeurP : Heuristic P | 1 |
352 | FERT : Fixed Error Randomized Time | 1 |
353 | WHILE : While programs and some restrictions | 1 |
354 | SIZE(f(n)) : Circuit Size f(n) | 1 |
355 | QMIPle : Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement | 1 |
356 | SO[LFP] : Second-Order logic with least fixed point | 1 |
357 | GAN-SPACE(f(n)) : Games Against Nature f(n)-Space | 1 |
358 | DTISP(t(n),s(n)) : Simultaneous t(n)-Time and s(n)-Space | 1 |
359 | UE : Unambiguous Exponential-Time With Linear Exponent | 1 |
360 | WAPPcc : Communication Complexity WAPP | 1 |
361 | QCPH : Quantum Classical PH | 1 |
362 | FO(DTC) : First-order with deterministic transitive closure | 1 |
363 | MAPOLYLOG : MA With Polylog Verifier | 1 |
364 | Θ2P : Alternate name for PNP[log] | 1 |
365 | P-RLOCAL : Polylogarithmic rounds in the Randomized LOCAL model | 1 |
366 | HkP : High Hierarchy In NP | 1 |
367 | SelfNP : Self-Witnessing NP | 1 |
368 | PrSPACE(f(n)) : Unbounded-Error Probabilistic f(n)-Space | 1 |
369 | mAL : Monotone AL | 1 |
370 | AVBPP : Average-Case BPP | 1 |
371 | CNP : Continuous NP | 1 |
372 | EP : NP with 2k Accepting Paths | 1 |
373 | PK : P With Kolmogorov-Complexity Oracle | 1 |
374 | VCk : Verification Class With A Circuit of Depth K | 1 |
375 | para-NL : Parameterized Nondeterministic Logspace | 1 |
376 | AxPP : Approximable in Probabilistic Polynomial Time | 1 |
377 | BQP-OBDD : Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram | 1 |
378 | FPERT : Fixed Parameter and Error Randomized Time | 1 |
379 | coRNC : Complement of RNC | 1 |
380 | BPPKT : BPP With Time-Bounded Kolmogorov Complexity Oracle | 1 |
381 | CC0 : Constant-Depth MODm Circuits | 1 |
382 | SZKh : SZK With Limited Help | 1 |
383 | P||QMA : P With Parallel Queries To QMA | 1 |
384 | UCC : Unique Connected Component | 1 |
385 | #L/poly : Nonuniform #L | 1 |
386 | EPTAS : Efficient Polynomial-Time Approximation Scheme | 1 |
387 | ⊕SAC1 : AC1 With Unbounded Parity Gates | 1 |
388 | SAC : Semi-Unbounded-Fanin AC | 1 |
389 | δ-BPP : δ-Semi-Random BPP | 1 |
390 | BQP/log : BQP With Logarithmic-Size Karp-Lipton Advice | 1 |
391 | UPostBPPcc : Unrestricted Communication Analogue of PostBPP | 1 |
392 | cofrIP : Complement of frIP | 1 |
393 | MaxSNP0 : Generating Class of MaxSNP | 1 |
394 | mTC0 : Monotone TC0 | 1 |
395 | LIN : Linear Time | 1 |
396 | OMA : Oblivious MA | 1 |
397 | SBQP : Small Bounded-Error Quantum Polynomial-Time | 1 |
398 | QMA+ : QMA With Non-Negative Amplitudes | 1 |
399 | PermUP : Self-Permuting UP | 1 |
400 | QH : Query Hierarchy Over NP | 1 |
401 | coNQP : Complement of NQP | 1 |
402 | RHL : Randomized Halting Logarithmic-Space | 1 |
403 | AUC-SPACE(f(n)) : Randomized Alternating f(n)-Space | 1 |
404 | RSPACE(f(n)) : Randomized f(n)-Space | 1 |
405 | UPcc : Communication Complexity UP | 1 |
406 | PromiseUP : Promise-Problem UP | 1 |
407 | AH : Arithmetic Hierarchy | 1 |
408 | PQMA[log] : P With Log QMA Queries | 1 |
409 | P-LOCAL : Polylogarithmic rounds in the LOCAL model | 1 |
410 | NIPZK : Non-Interactive PZK | 1 |
411 | EQPK : Exact Quantum Polynomial-Time with Gate Set K | 1 |
412 | NE/poly : Nonuniform NE | 1 |
413 | QNC0/qpoly : Quantum NC0 With Polynomial-Size Quantum Advice | 1 |
414 | NLT : Nearly Linear Time | 1 |
415 | PL∞ : Polynomially-Bounded L∞-1 Spectral Norm | 1 |
416 | CLOG : Continuous Logarithmic-Time | 1 |
417 | HVSZK : Honest-Verifier SZK | 1 |
418 | MIPEXP : Exponential-Time Multi-Prover Interactive Proof | 1 |
419 | ModP : ModkP With Arbitrary k | 1 |
420 | BPQP : Bounded-Error Probabilistic QP | 1 |
421 | PromiseRP : Promise-Problem RP | 1 |
422 | CSIZE(f(n)) : Circuit Size f(n) | 1 |
423 | VNCk : Valiant NC Over Field k | 1 |
424 | QMAlog : QMA With Logarithmic-Size Proofs | 1 |
425 | F-TIME(f(n)) : Provable DTIME(f(n)) For Formal System F | 1 |
426 | NT* : Near-Testable With Forest Ordering | 1 |
427 | coSL : Complement of SL | 1 |
428 | FPTnu : Fixed-Parameter Tractable (nonuniform) | 1 |
429 | compIP : Competitive IP Proof System | 1 |
430 | RHSPACE(f(n)) : One-Sided Error Halting Probabilistic f(n)-Space | 1 |
431 | FPTsu : Fixed-Parameter Tractable (strongly uniform) | 1 |
432 | para-NL[f log] : Parameterized Nondeterministic Logspace | 1 |
433 | AW[P] : Alternating W[P] | 1 |
434 | LogFew : Logspace-Bounded Few | 1 |
435 | Dyn-FO : Dynamic FO | 1 |
436 | ZPPcc : Communication Complexity ZPP | 1 |
437 | F-TAPE(f(n)) : Provable DSPACE(f(n)) For Formal System F | 1 |
438 | AW[t] : Alternating W[t] | 1 |
439 | HeurBPP : Heuristic BPP | 1 |
440 | LogFewNL : Logspace-Bounded FewP | 1 |
441 | RNC1 : Randomized NC1 | 1 |
442 | IPP : Unbounded IP | 1 |
443 | PostBPP : BPP With Postselection | 1 |
444 | PSPACE/poly : PSPACE With Polynomial-Size Advice | 1 |
445 | PL1 : Polynomially-Bounded L1 Spectral Norm | 1 |
446 | EEE : Triple-Exponential Time With Linear Exponent | 1 |
447 | PT/WK(f(n),g(n)) : Parallel Time f(n) / Work g(n) | 1 |
448 | S≠ : Exclusive Stochastic Languages | 1 |
449 | NLIN : Nondeterministic LIN | 1 |
450 | QNC0/🐱 : Quantum NC0 With Polynomial-Size Quantum Advice | 1 |
451 | Dyn-ThC0 : Dynamic Threshold Circuits | 1 |
452 | SO[TC] : Second-Order logic with transitive closure | 1 |
453 | FPRAS : Fully Polynomial Randomized Approximation Scheme | 1 |