601 classes
Symbols
0-1-NPC : Binary Restriction of NP Over The Complex Numbers
1NAuxPDAp : One-Way NAuxPDAp
2-EXP : Double-Exponential Time
3SUM-hard : Problems hard for 3SUM
#AC0 : Sharp-AC0
#GA : Graph Automorphism
#L : Sharp-L
#L/poly : Nonuniform #L
#P : Sharp-P or Number-P
#W[t] : Sharp-W[t]
⊕EXP : Parity EXP
⊕L : Parity L
⊕L/poly : Nonuniform ⊕L
⊕P : Parity P
⊕Pcc : Communication Complexity ⊕P
⊕SAC0 : AC0 With Unbounded Parity Gates
⊕SAC1 : AC1 With Unbounded Parity Gates
A
A0PP : One-Sided Analog of AWPP
AC : Unbounded Fanin Polylogarithmic-Depth Circuits
AC0 : Unbounded Fanin Constant-Depth Circuits
AC0[m] : AC0 With MOD m Gates
AC1 : Unbounded Fanin Log-Depth Circuits
ACC0 : AC0 With Arbitrary MOD Gates
Ack : Ackermann Time
AH : Arithmetic Hierarchy
AL : Alternating L
ALL : The Class of All Languages
ALOGTIME : Logarithmic time alternating RAM
AlgP/poly : Polynomial-Size Algebraic Circuits
Almost-NP : Languages Almost Surely in NPA
Almost-P : Languages Almost Surely in PA
Almost-PSPACE : Languages Almost Surely in PSPACEA
AM : Arthur-Merlin
AMcc : Communication Complexity AM
AMEXP : Exponential-Time AM
AM ∩ coAM :
AM[polylog] : AM With Polylog Rounds
AmpMP : Amplifiable MP
AmpP-BQP : BQP Restricted To AmpP States
AP : Alternating P
APP : Amplified PP
APSPACE : Alternating PSPACE
APX : Approximable
AUC-SPACE(f(n)) : Randomized Alternating f(n)-Space
AuxPDA : Auxiliary Pushdown Automata
AVBPP : Average-Case BPP
AvgE : Average Exponential-Time With Linear Exponent
AvgP : Average Polynomial-Time
AW[P] : Alternating W[P]
AWPP : Almost WPP
AW[SAT] : Alternating W[SAT]
AW[*] : Alternating W[*]
AW[t] : Alternating W[t]
AxP : Approximable in Polynomial Time
AxPP : Approximable in Probabilistic Polynomial Time
B
βFOLL : Limited-Nondeterminism FOLL
βMAC0 : Limited-Nondeterminism MAC0
βP : Limited-Nondeterminism NP
BC=P : Bounded-Error C=P
BH : Boolean Hierarchy Over NP
BPd(P) : Polynomial Size d-Times-Only Branching Program
BPE : Bounded-Error Probabilistic E
BPEE : Bounded-Error Probabilistic EE
BPHSPACE(f(n)) : Bounded-Error Halting Probabilistic f(n)-Space
BPL : Bounded-Error Probabilistic L
BP•L : Bounded-Error Probabilistic L with Two Way Access to Randomness
BP•NP : Probabilistic NP
BPP : Bounded-Error Probabilistic Polynomial-Time
BPPcc : Communication Complexity BPP
BPP
cc:BPPcc in NOF model,
players
BPPKT : BPP With Time-Bounded Kolmogorov Complexity Oracle
BPP/log : BPP With Logarithmic Karp-Lipton Advice
BPP/mlog : BPP With Logarithmic Deterministic Merlin-Like Advice
BPP//log : BPP With Logarithmic Randomness-Dependent Advice
BPP/rlog : BPP With Logarithmic Probabilistically Sampled Random Advice
BPP-OBDD : Polynomial-Size Bounded-Error Ordered Binary Decision Diagram
BPPpath : Threshold BPP
BPQP : Bounded-Error Probabilistic QP
BPSPACE(f(n)) : Bounded-Error Probabilistic f(n)-Space
BPTIME(f(n)) : Bounded-Error Probabilistic f(n)-Time
BQL : Bounded-Error Quantum Logspace
BQNC : Alternate Name for QNC
BQNP : Alternate Name for QMA
BQP : Bounded-Error Quantum Polynomial-Time
BQP/log : BQP With Logarithmic-Size Karp-Lipton Advice
BQP/poly : BQP With Polynomial-Size Karp-Lipton Advice
BQP/mlog : BQP With Logarithmic-Size Deterministic Merlin-Like Advice
BQP/mpoly : BQP With Polynomial-Size Deterministic Merlin-Like Advice
BQP/qlog : BQP With Logarithmic-Size Quantum Advice
BQP/qpoly : BQP With Polynomial-Size Quantum Advice
BQP-OBDD : Polynomial-Size Bounded-Error Quantum Ordered Binary Decision Diagram
BQPSPACE : Bounded-Error Quantum PSPACE
BQTIME(f(n)) : Bounded-Error Quantum f(n)-Time
BQPtt/poly : BQP/mpoly With Truth-Table Queries
k-BWBP : Bounded-Width Branching Program
C
C=AC0 : Exact-Counting AC0
C=L : Exact-Counting L
C=P : Exact-Counting Polynomial-Time
CC : Comparator Circuits
CC0 : Constant-Depth MODm Circuits
CFL : Context-Free Languages
CH : Counting Hierarchy
Check : Checkable Languages
CkP : kth Level of CH
CL : Catalytic Logspace
CL#P : Cluster Sharp-P
CLOG : Continuous Logarithmic-Time
CNP : Continuous NP
coAM : Complement of AM
coC=P : Complement of C=P
cofrIP : Complement of frIP
Coh : Coherent Languages
coMA : Complement of MA
coModkP : Complement of ModkP
compIP : Competitive IP Proof System
compNP : Competitive NP Proof System
coNE : Complement of NE
coNEXP : Complement of NEXP
coNL : Complement of NL
coNP : Complement of NP
coNPC : coNP-Complete
coNPcc : Complement of NPcc
coNP/poly : Complement of NP/poly
coNQP : Complement of NQP
coRE : Complement of RE
coRNC : Complement of RNC
coRP : Complement of RP
coSL : Complement of SL
coSPARSE : Complement of SPARSE
coUCC : Complement of UCC
coUP : Complement of UP
CP : Continuous P
cq-Σ2 : Classical-Quantum-Σ2P
CSIZE(f(n)) : Circuit Size f(n)
CSL : Context Sensitive Languages
CSP : Constraint Satisfaction Problems
CSPACE : Catalytic space
CZK : Computational Zero-Knowledge
D
D#P : Alternate Name for P#P
DCFL : Deterministic CFL
Δ2P : P With NP Oracle
δ-BPP : δ-Semi-Random BPP
δ-RP : δ-Semi-Random RP
DET : Determinant
DiffAC0 : Difference #AC0
DistributionPH : Distribution PH
DisNP : Disjoint NP Pairs
DistNP : Distributional NP
DP or Dp : Difference Polynomial-Time
DQC1 : Deterministic Quantum Computing with 1 Clean Bit
DQP : Dynamical Quantum Polynomial-Time
DSPACE(f(n)) : Deterministic f(n)-Space
DTIME(f(n)) : Deterministic f(n)-Time
DTISP(t(n),s(n)) : Simultaneous t(n)-Time and s(n)-Space
Dyn-FO : Dynamic FO
Dyn-ThC0 : Dynamic Threshold Circuits
E
E : Exponential Time With Linear Exponent
EE : Double-Exponential Time With Linear Exponent
EEE : Triple-Exponential Time With Linear Exponent
EESPACE : Double-Exponential Space With Linear Exponent
EEXP : Double-Exponential Time
EH : Exponential-Time Hierarchy With Linear Exponent
ELEMENTARY : Finitely Iterated Exponential Time
ELkP : Extended Low Hierarchy
EP : NP with 2k Accepting Paths
EPTAS : Efficient Polynomial-Time Approximation Scheme
k-EQBP : Width-k Polynomial-Time Exact Quantum Branching Programs
EQP : Exact Quantum Polynomial-Time
EQPK : Exact Quantum Polynomial-Time with Gate Set K
EQTIME(f(n)) : Exact Quantum f(n)-Time
ESPACE : Exponential Space With Linear Exponent
∃BPP : BPP With Existential Operator
∃NISZK : NISZK With Existential Operator
∃R : Existential theory of the reals
EXP : Exponential Time
EXP/poly : Exponential Time With Polynomial-Size Advice
EXPSPACE : Exponential Space
F
FBPP : Function BPP
FBQP : Function BQP
FERT : Fixed Error Randomized Time
FPERT : Fixed Parameter and Error Randomized Time
Few : FewP With Flexible Acceptance Mechanism
FewEXP : NEXP With Few Witnesses
FewP : NP With Few Witnesses
FH : Fourier Hierarchy
FIXP : Fixed Point
FNL : Function NL
FNL/poly : Nonuniform FNL
FNP : Function NP
FO : First-Order logic
FO(DTC) : First-order with deterministic transitive closure
FO(LFP) : First-order with least fixed point
FO(PFP) : First-order with partial fixed point
FO(TC) : First-order with transitive closure
FO[
] : Iterated First-Order logic
FOLL : First-Order log log n
FP : Function Polynomial-Time
FPNP[log] : FP With Logarithmically Many Queries To NP
FPL : Fixed Parameter Linear
FPR : Fixed-Parameter Randomized
FPRAS : Fully Polynomial Randomized Approximation Scheme
FPT : Fixed-Parameter Tractable
FPTnu : Fixed-Parameter Tractable (nonuniform)
FPTsu : Fixed-Parameter Tractable (strongly uniform)
FPTAS : Fully Polynomial-Time Approximation Scheme
FQMA : Function QMA
frIP : Function-Restricted IP Proof Systems
F-TAPE(f(n)) : Provable DSPACE(f(n)) For Formal System F
F-TIME(f(n)) : Provable DTIME(f(n)) For Formal System F
G
GA : Graph Automorphism
GAN-SPACE(f(n)) : Games Against Nature f(n)-Space
GapAC0 : Gap #AC0
GapL : Gap Logarithmic-Space
GapP : Gap Polynomial-Time
GC(s(n),C) : Guess and Check
GCSL : Growing CSL
GI : Graph Isomorphism
GLO : Guaranteed Local Optima
GPCD(r(n),q(n)) : Generalized Probabilistically Checkable Debate
G[t] : Stratification of Fixed-Parameter Tractable Problems
H
HalfP : RP With Exactly Half Acceptance
HeurBPP : Heuristic BPP
HeurBPTIME(f(n)) : Heuristic BPTIME(f(n))
HeurDTIME
(f(n)) : Heuristic DTIME
HeurP : Heuristic P
HeurPP : Heuristic PP
HeurNTIME
(f(n)) : Heuristic NTIME
HkP : High Hierarchy In NP
HO : High-Order logic
HVPZK : Honest-Verifier PZK
HVSZK : Honest-Verifier SZK
I
IC[log,poly] : Logarithmic Instance Complexity, Polynomial Time
IP : Interactive Proof Systems
IOP : Interactive Oracle Proof
IPP : Unbounded IP
IP[polylog] :
J
K
K : Feasibly recursive functions
L
L : Logarithmic Space
LC0 : Unbounded Fanin Linear Size (gates) Constant-Depth Circuits
LH : Logarithmic Time Hierarchy
LIN : Linear Time
LkP : Low Hierarchy In NP
LOGCFL : Logarithmically Reducible to CFL
LogFew : Logspace-Bounded Few
LogFewNL : Logspace-Bounded FewP
LOGLOG : loglog Space
LOGNP : Logarithmically-Restricted NP
LOGSNP : Logarithmically-Restricted SNP
L/poly : Nonuniform Logarithmic Space
LWPP : Length-Dependent Wide PP
M
MA : Merlin-Arthur
MAcc : Communication Complexity MA
MA' : Sparse MA
MAC0 : Majority of AC0
MAE : Exponential-Time MA With Linear Exponent
MAEXP : Exponential-Time MA
mAL : Monotone AL
MAPOLYLOG : MA With Polylog Verifier
MaxNP : Maximization NP
MaxPB : MaxNP Polynomially Bounded
MaxSNP : Maximization SNP
MaxSNP0 : Generating Class of MaxSNP
mcoNL : Complement of mNL
MinPB : MinNP Polynomially Bounded
MIP : Multi-Prover Interactive Proof
MIP* : MIP With Quantum Provers
MIPns : MIP with Non-Signaling Provers
MIPEXP : Exponential-Time Multi-Prover Interactive Proof
(Mk)P : Acceptance Mechanism by Monoid Mk
mL : Monotone L
MM : Problems reducible to matrix multiplication
MMSNP : Monadic Monotone SNP
mNC1 : Monotone NC1
mNL : Monotone NL
mNP : Monotone NP
ModkL : Mod-k L
ModL : ModL
ModkP : Mod-k Polynomial-Time
ModP : ModkP With Arbitrary k
ModPH : Modular Counting Hierarchy
ModZkL : Restricted ModkL
mP : Monotone P
MP : Middle-Bit P
MPC : Monotone Planar Circuits
mP/poly : Monotone P/poly
mTC0 : Monotone TC0
N
naCQP : non-adaptive Collapse-free Quantum Polynomial time
NAuxPDAp : Nondeterministic Auxiliary Pushdown Automata
NC : Nick's Class
NC0 : Level 0 of NC
NC1 : Level 1 of NC
NC2 : Level 2 of NC
NE : Nondeterministic E
Nearly-P : Languages Superpolynomially Close to P
NE/poly : Nonuniform NE
NEE : Nondeterministic EE
NEEE : Nondeterministic EEE
NEEXP : Nondeterministic EEXP
NEXP : Nondeterministic EXP
NEXP/poly : Nonuniform NEXP
NIPZK : Non-Interactive PZK
NIQSZK : Non-Interactive QSZK
NISZK : Non-Interactive SZK
NISZKh : NISZK With Limited Help
NL : Nondeterministic Logarithmic-Space
NL/poly : Nonuniform NL
NLO : NL Optimization Problems
NLOG : NL With Nondeterministic Oracle Tape
NLIN : Nondeterministic LIN
NLT : Nearly Linear Time
NMCL : Nondeterministic Moore-Crutchfield Languages
NNLT : Nondeterministic Nearly Linear Time
NONE : The Empty Class
NP : Nondeterministic Polynomial-Time
NPC : NP-Complete
NPC : NP Over The Complex Numbers
NPcc : Communication Complexity NP
NP
cc:NPcc in NOF model,
players
NPI : NP-Intermediate
NP ∩ coNP :
(NP ∩ coNP)/poly : Nonuniform NP ∩ coNP
NP/log : NP With Logarithmic Advice
NPMV : NP Multiple Value
NPMV-sel : NPMV Selective
NPMVt : NPMV Total
NPMVt-sel : NPMVt Selective
NPO : NP Optimization
NPOPB : NPO Polynomially Bounded
NP/poly : Nonuniform NP
(NP,P-samplable) : Average NP With Samplable Distributions
NPR : NP Over The Reals
NPSPACE : Nondeterministic PSPACE
NPSV : NP Single Value
NPSV-sel : NPSV Selective
NPSVt : NPSV Total
NPSVt-sel : NPSVt Selective
NQL : Nondet Quasi-Linear
NQL : Nondeterministic Quantum Languages
NQP : Nondeterministic Quantum Polynomial-Time
NSPACE(f(n)) : Nondeterministic f(n)-Space
NT : Near-Testable
NT* : Near-Testable With Forest Ordering
NTIME(f(n)) : Nondeterministic f(n)-Time
O
OIP : Oblivious IP
OMA : Oblivious MA
ONP : Oblivious NP
OptP : Optimum Polynomial-Time
O2P : Second Level of the Oblivious Symmetric Hierarchy
P
P : Polynomial-Time
P/log : P With Logarithmic Advice
P/poly : Nonuniform Polynomial-Time
P#P : P With #P Oracle
P#P[1] : P With Single Query To #P Oracle
PCTC : P With Closed Time Curves
para- : Parameterized Complexity
para-L : Parameterized Logspace
para-NL : Parameterized Nondeterministic Logspace
para-NL[f log] : Parameterized Nondeterministic Logspace
para-P : Parameterized Polynomial time.
PAC0 : Probabilistic AC0
PBP : Polynomial-Size Branching Program
k-PBP : Polynomial-Size Width-k Branching Program
PC : Polynomial-Time Over The Complex Numbers
Pcc : Communication Complexity P
P
cc:Pcc in NOF model,
players
PCD(r(n),q(n)) : Probabilistically Checkable Debate
P-Close : Problems Close to P
PCP(r(n),q(n)) : Probabilistically Checkable Proof
PDQP : Product Dynamical Quantum Polynomial time
PermUP : Self-Permuting UP
PEXP : Probabilistic Exponential-Time
PF : Alternate Name for FP
PFCHK(t(n)) : Proof-Checker
PH : Polynomial-Time Hierarchy
PHcc : Communication Complexity PH
Φ2P : Second Level of the Symmetric Hierarchy, Alternative Definition
PhP : Physical Polynomial-Time
Π2P : coNP With NP Oracle
PINC : Polynomial Ignorance of Names of Classes
PIO : Polynomial Input Output
PK : P With Kolmogorov-Complexity Oracle
PKC : Perfect Knowledge Complexity
PL : Probabilistic L
PL1 : Polynomially-Bounded L1 Spectral Norm
PL∞ : Polynomially-Bounded L∞-1 Spectral Norm
PLF : Polynomial Leaf
PLL : Polynomial Local Lemma
P-LOCAL : Polylogarithmic rounds in the LOCAL model
P-RLOCAL : Polylogarithmic rounds in the Randomized LOCAL model
PLS : Polynomial Local Search
PNP : P With Oracle Access To NP
PNPcc : Communication Complexity PNP
P||NP : P With Parallel Queries To NP
PNP[k] : P With k NP Queries(for constant k)
PNP[log] : P With Log NP Queries
PNP[log^2] : P With Log2 NP Queries
P-OBDD : Polynomial-Size Ordered Binary Decision Diagram
PODN : Polynomial Odd Degree Node
polyL : Polylogarithmic Space
PostBPP : BPP With Postselection
PostBPPcc : Communication Complexity PostBPP
PostBQP : BQP With Postselection
PP : Probabilistic Polynomial-Time
PPcc : Communication Complexity PP
PP/poly : Nonuniform PP
PPA : Polynomial Parity Argument
PPAD : Polynomial Parity Argument (Directed)
PPADS : Polynomial Parity Argument (Directed, Sink)
PPP : Polynomial Pigeonhole Principle
PPP : P With PP Oracle
PQMA[log] : P With Log QMA Queries
P||QMA : P With Parallel Queries To QMA
PQP : Probabilistic Quantum Polynomial-Time
PQUERY : PSPACE With Polynomial Queries
PPSPACE : Probabilistic PSPACE
PR : Primitive Recursive Functions
PR : Polynomial-Time Over The Reals
PrHSPACE(f(n)) : Unbounded-Error Halting Probabilistic f(n)-Space
PromiseBPP : Promise-Problem BPP
PromiseBQP : Promise-Problem BQP
PromiseP : Promise-Problem P
PromiseRP : Promise-Problem RP
PromiseUP : Promise-Problem UP
PrSPACE(f(n)) : Unbounded-Error Probabilistic f(n)-Space
P-Sel : P-Selective Sets
PSK : Polynomial Sink
PSPACE : Polynomial-Space
PSPACEcc : Communication Complexity PSPACE
PSPACE/poly : PSPACE With Polynomial-Size Advice
PT1 : Polynomial Threshold Functions
PTAPE : Archaic for PSPACE
PTAS : Polynomial-Time Approximation Scheme
PT/WK(f(n),g(n)) : Parallel Time f(n) / Work g(n)
PureSuperQMA : A pure-state analog of SuperQMA
PZK : Perfect Zero Knowledge
Q
Q : Quasi-Realtime Languages
QAC0 : Quantum AC0
QAC0[m] : Quantum AC0[m]
QACC0 : Quantum ACC0
QACf0 : QAC0 With Fanout
QAM : Quantum AM
QCFL : Quantum CFL
QCMA : Quantum Classical MA
QCPH : Quantum Classical PH
QEPH : Entangled Quantum PH
QH : Query Hierarchy Over NP
QIP : Quantum IP
QIP[2] : 2-Message Quantum IP
QL : Quasi-Linear
QMA : Quantum MA
QMA-plus : QMA With Super-Verifier
QMA+ : QMA With Non-Negative Amplitudes
QMA(2) : Quantum MA With Multiple Certificates
QMA1 : One Sided QMA
QMAlog : QMA With Logarithmic-Size Proofs
QMA+(2) : QMA(2) With Non-Negative Amplitudes
QMAM : Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs
QMA/qpoly : QMA With Polynomial-Size Quantum Advice
QMIP : Quantum Multi-Prover Interactive Proofs
QMIPle : Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement
QMIPne : Quantum Multi-Prover Interactive Proofs With No Prior Entanglement
QNC : Quantum NC
QNC0 : Quantum NC0
QNC0/qpoly : Quantum NC0 With Polynomial-Size Quantum Advice
QNC0/🐱 : Quantum NC0 With Polynomial-Size Quantum Advice
QNCf0 : Quantum NC0 With Unbounded Fanout
QNC1 : Quantum NC1
QP : Quasipolynomial-Time
QPH : Quantum PH
QPIP : Quantum Prover Interactive Proof
QPLIN : Linear Quasipolynomial-Time
QPSPACE : Quasipolynomial-Space
QRG : Quantum Refereed Games
QRG(k) : k-turn Quantum Refereed Games
QRG(2) : Two-turn (one-round) Quantum Refereed Games
QRG(1) : One-turn Quantum Refereed Games
QRL : Quantum Regular Languages
QSZK : Quantum Statistical Zero-Knowledge
R
R : Recursive Languages
RBQP : Strict Quantum RP
RE : Recursively Enumerable Languages
REG : Regular Languages
RevSPACE(f(n)) : Reversible f(n)-Space
RG : Refereed Games
RG(k) : k-turn Refereed Games
RG(2) : Two-turn (one-round) Refereed Games
RG(1) : One-turn Refereed Games
RHL : Randomized Halting Logarithmic-Space
RHSPACE(f(n)) : One-Sided Error Halting Probabilistic f(n)-Space
RL : Randomized Logarithmic-Space
RNC : Randomized NC
RNC1 : Randomized NC1
RP : Randomized Polynomial-Time
RPcc : Communication Complexity RP
RP
cc:Randomized P
cc
RPP : Restricted Pseudo Polynomial-Time
RQP : One-sided Error Extension of EQP
RSPACE(f(n)) : Randomized f(n)-Space
S
S≠ : Exclusive Stochastic Languages
S2P : Second Level of the Symmetric Hierarchy
S2E : Second Level of the Symmetric Linear Exponent Hierarchy
S2-EXP•PNP : Don't Ask
SAC : Semi-Unbounded-Fanin AC
SAC0 : Semi-Unbounded-Fanin AC0
SAPTIME : Stochastic Alternating Polynomial-Time
SBP : Small Bounded-Error Probability
SBPcc : Communication Complexity SBP
SBQP : Small Bounded-Error Quantum Polynomial-Time
SC : Steve's Class
SE : Subexponentially-Solvable Search Problems
SEH : Strong Exponential Hierarchy
SelfNP : Self-Witnessing NP
SFk : Width-k Bottleneck Turing Machines
Σ2P : NP With NP Oracle
SIZE(f(n)) : Circuit Size f(n)
SKC : Statistical Knowledge Complexity
SL : Symmetric Logarithmic-Space
SLICEWISE PSPACE : Parametrized PSPACE
SNP : Strict NP
SO : Second-Order logic
SO(Horn) : Second-order in Horn form
SO(Krom) : Second-order in Krom form
SO[LFP] : Second-Order logic with least fixed point
SO[TC] : Second-Order logic with transitive closure
SO[
] : Iterated Second-Order logic
SP : Semi-Efficient Parallel
span-L : Span Logarithmic-Space
span-P : Span Polynomial-Time
SPARSE : Sparse Languages
SPL : Stoic PL
SPP : Stoic PP
SQG : Short Quantum Games
SUBEXP : Deterministic Subexponential-Time
symP : Alternate Name for S2P
SZK : Statistical Zero Knowledge
SZKh : SZK With Limited Help
T
TALLY : Tally Languages
TC : Threshold Circuits
TC0 : Constant-Depth Threshold Circuits
TC0(FOLL) : Languages that are TC0 Turing reducible to FOLL
TC1 : Log-depth Threshold Circuits
TFNP : Total Function NP
Θ2P : Alternate name for PNP[log]
TI : Tensor Isomorphism
TOWER : Iterated Exponential Time
TreeBQP : BQP Restricted To Tree States
TREE-REGULAR : Regular Tree-Valued Languages
U
UAMcc : Unambiguous Arthur-Merlin Communication Complexity
UAP : Unambiguous Alternating Polynomial-Time
UCC : Unique Connected Component
UCFL : Unambiguous CFL
UE : Unambiguous Exponential-Time With Linear Exponent
UL : Unambiguous L
UL/poly : Nonuniform UL
UP : Unambiguous Polynomial-Time
UPcc : Communication Complexity UP
UPostBPPcc : Unrestricted Communication Analogue of PostBPP
UPPcc : Unrestricted Communication Analogue of PP
US : Unique Polynomial-Time
USBPcc : Unrestricted Communication Analogue of SBP
UWAPPcc : Unrestricted Communication Analogue of WAPP
V
VCk : Verification Class With A Circuit of Depth K
VCor : Verification Class With OR
VNCk : Valiant NC Over Field k
VNPk : Valiant NP Over Field k
VPk : Valiant P Over Field k
VPL : Visibly pushdown languages
VQPk : Valiant QP Over Field k
W
W[1] : Weighted Analogue of NP
WAPP : Weak Almost-Wide PP
WAPPcc : Communication Complexity WAPP
WHILE : While programs and some restrictions
WLC0 : Unbounded Fanin Linear Size (wires) Constant-Depth Circuits
W[P] : Weighted Circuit Satisfiability
WPP : Wide PP
W[SAT] : Weighted Satisfiability
W[*] : Union of W[t]'s
W[t] : Nondeterministic Fixed-Parameter Hierarchy
W*[t] : W[t] With Parameter-Dependent Depth
X
XOR-MIP*[2,1] : MIP*[2,1] With 1-Bit Proofs
XL : Fixed-Parameter Logspace for Each Parameter
XNL : Fixed-Parameter Nondeterministic Logspace for Each Parameter
XNLP : Fixed-Parameter Nondeterministic Logspace and Polytime for Each Parameter
XP : Fixed-Parameter Tractable for Each Parameter
XPuniform : Uniform XP
Y
YACC : Yet Another Complexity Class
YP : Your Polynomial-Time or Yaroslav-Percival
YP* : Yaroslav-Percival Star
YPP : Yaroslav BPP
YQP : Yaroslav BQP
YQP* : Yaroslav BQP star
YQP*/poly : YQP* With Polynomial-Size Advice
Z
ZAMcc : Zero-Information Arthur-Merlin Communication Complexity
ZBQP : Strict Quantum ZPP
ZK : Zero-Knowledge (see CZK)
ZPE : Zero-Error Probabilistic E
ZP•L : Zero-Error Probabilistic L with Two Way Access to Randomness
ZPP : Zero-Error Probabilistic Polynomial-Time
ZPPcc : Communication Complexity ZPP
ZPTIME(f(n)) : Zero-Error Probabilistic f(n)-Time
ZQP : Zero-Error Extension Of EQP