603 classes

Symbols

0-1-NP_C : Binary Restriction of NP Over The Complex Numbers
1NAuxPDA^p : One-Way NAuxPDA^p
2-EXP : Double-Exponential Time
3SUM-hard : Problems hard for 3SUM
#AC⁰ : Sharp-AC⁰
#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
⊕P^cc : Communication Complexity ⊕P
⊕SAC⁰ : AC⁰ With Unbounded Parity Gates
⊕SAC¹ : AC¹ With Unbounded Parity Gates

A

A₀PP : One-Sided Analog of AWPP
AC : Unbounded Fanin Polylogarithmic-Depth Circuits
AC⁰ : Unbounded Fanin Constant-Depth Circuits
AC⁰[m] : AC⁰ With MOD m Gates
AC¹ : Unbounded Fanin Log-Depth Circuits
ACC⁰ : AC⁰ 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 NP^A
Almost-P : Languages Almost Surely in P^A
Almost-PSPACE : Languages Almost Surely in PSPACE^A
AM : Arthur-Merlin
AM^cc : Communication Complexity AM
AM_EXP : Exponential-Time AM
AM ∩ coAM : The intersection of AM and 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
βMAC⁰ : Limited-Nondeterminism MAC⁰
βP : Limited-Nondeterminism NP
BC₌P : Bounded-Error C₌P
BH : Boolean Hierarchy Over NP
BP_d(P) : Polynomial Size d-Times-Only Branching Program
BPE : Bounded-Error Probabilistic E
BPEE : Bounded-Error Probabilistic EE
BP_HSPACE(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
BPP^cc : Communication Complexity BPP
BPP_{$k {\displaystyle k}$}^cc : BPP^cc in NOF model, $k {\displaystyle k}$ players
BPP^KT : 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
BPP_path : 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
BQP_tt/poly : BQP/mpoly With Truth-Table Queries
k-BWBP : Bounded-Width Branching Program

C

C₌AC⁰ : Exact-Counting AC⁰
C₌L : Exact-Counting L
C₌P : Exact-Counting Polynomial-Time
CC : Comparator Circuits
CC⁰ : Constant-Depth MOD_m Circuits
CFL : Context-Free Languages
CH : Counting Hierarchy
Check : Checkable Languages
C_kP : k^th 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
coMod_kP : Complement of Mod_kP
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
coNP^cc : Complement of NP^cc
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-Σ₂ : Classical-Quantum-Σ₂P
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
Δ₂P : P With NP Oracle
δ-BPP : δ-Semi-Random BPP
δ-RP : δ-Semi-Random RP
DET : Determinant
DiffAC⁰ : Difference #AC⁰
DistributionPH : Distribution PH
DisNP : Disjoint NP Pairs
DistNP : Distributional NP
DP or D^p : 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-ThC⁰ : 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
EL_kP : Extended Low Hierarchy
EP : NP with 2^k Accepting Paths
EPTAS : Efficient Polynomial-Time Approximation Scheme
k-EQBP : Width-k Polynomial-Time Exact Quantum Branching Programs
EQP : Exact Quantum Polynomial-Time
EQP_K : 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[ $t(n)$ ] : Iterated First-Order logic
FOLL : First-Order log log n
FP : Function Polynomial-Time
FP^NP[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
FPT_nu : Fixed-Parameter Tractable (nonuniform)
FPT_su : 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
GapAC⁰ : Gap #AC⁰
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_$\delta$(f(n)) : Heuristic DTIME
HeurP : Heuristic P
HeurPP : Heuristic PP
HeurNTIME_$\delta$(f(n)) : Heuristic NTIME
H_kP : 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] : IP With Polylog Rounds

J

K

K : Feasibly recursive functions

L

L : Logarithmic Space
LC⁰ : Unbounded Fanin Linear Size (gates) Constant-Depth Circuits
LH : Logarithmic Time Hierarchy
LIN : Linear Time
L_kP : 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
MA^cc : Communication Complexity MA
MA' : Sparse MA
MAC⁰ : Majority of AC⁰
MA_E : Exponential-Time MA With Linear Exponent
MA_EXP : Exponential-Time MA
mAL : Monotone AL
MA_POLYLOG : MA With Polylog Verifier
MaxNP : Maximization NP
MaxPB : MaxNP Polynomially Bounded
MaxSNP : Maximization SNP
MaxSNP₀ : Generating Class of MaxSNP
mcoNL : Complement of mNL
MinPB : MinNP Polynomially Bounded
MIP : Multi-Prover Interactive Proof
MIP* : MIP With Quantum Provers
MIP^ns : MIP with Non-Signaling Provers
MIP_EXP : Exponential-Time Multi-Prover Interactive Proof
(M_k)P : Acceptance Mechanism by Monoid M_k
mL : Monotone L
MM : Problems reducible to matrix multiplication
MMSNP : Monadic Monotone SNP
mNC¹ : Monotone NC¹
mNL : Monotone NL
mNP : Monotone NP
Mod_kL : Mod-k L
ModL : ModL
Mod_kP : Mod-k Polynomial-Time
ModP : Mod_kP With Arbitrary k
ModPH : Modular Counting Hierarchy
ModZ_kL : Restricted Mod_kL
mP : Monotone P
MP : Middle-Bit P
MPC : Monotone Planar Circuits
mP/poly : Monotone P/poly
mTC⁰ : Monotone TC⁰

N

naCQP : non-adaptive Collapse-free Quantum Polynomial time
NAuxPDA^p : Nondeterministic Auxiliary Pushdown Automata
NC : Nick's Class
NC⁰ : Level 0 of NC
NC¹ : Level 1 of NC
NC² : 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
NISZK_h : 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
NP_C : NP Over The Complex Numbers
NP^cc : Communication Complexity NP
NP_{$k {\displaystyle k}$}^cc : NP^cc in NOF model, $k {\displaystyle k}$ players
NPI : NP-Intermediate
NP ∩ coNP : The intersection of NP and coNP
(NP ∩ coNP)/poly : Nonuniform NP ∩ coNP
NP/log : NP With Logarithmic Advice
NPMV : NP Multiple Value
NPMV-sel : NPMV Selective
NPMV_t : NPMV Total
NPMV_t-sel : NPMV_t Selective
NPO : NP Optimization
NPOPB : NPO Polynomially Bounded
NP/poly : Nonuniform NP
(NP,P-samplable) : Average NP With Samplable Distributions
NP_R : NP Over The Reals
NPSPACE : Nondeterministic PSPACE
NPSV : NP Single Value
NPSV-sel : NPSV Selective
NPSV_t : NPSV Total
NPSV_t-sel : NPSV_t 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
O₂P : 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
P_CTC : 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.
PAC⁰ : Probabilistic AC⁰
PBP : Polynomial-Size Branching Program
k-PBP : Polynomial-Size Width-k Branching Program
P_C : Polynomial-Time Over The Complex Numbers
P^cc : Communication Complexity P
P_{$k {\displaystyle k}$}^cc : P^cc in NOF model, $k {\displaystyle k}$ 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
PH^cc : Communication Complexity PH
Φ₂P : Second Level of the Symmetric Hierarchy, Alternative Definition
PhP : Physical Polynomial-Time
Π₂P : coNP With NP Oracle
PINC : Polynomial Ignorance of Names of Classes
PIO : Polynomial Input Output
P^K : P With Kolmogorov-Complexity Oracle
PKC : Perfect Knowledge Complexity
PL : Probabilistic L
PL₁ : Polynomially-Bounded L₁ 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
P^NP : P With Oracle Access To NP
P^NPcc : Communication Complexity P^NP
P^||NP : P With Parallel Queries To NP
P^NP[k] : P With k NP Queries(for constant k)
P^NP[log] : P With Log NP Queries
P^{NP[log^2]} : P With Log² NP Queries
P-OBDD : Polynomial-Size Ordered Binary Decision Diagram
PODN : Polynomial Odd Degree Node
polyL : Polylogarithmic Space
PostBPP : BPP With Postselection
PostBPP^cc : Communication Complexity PostBPP
PostBQP : BQP With Postselection
PP : Probabilistic Polynomial-Time
PP^cc : 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
P^PP : P With PP Oracle
P^QMA[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
P_R : Polynomial-Time Over The Reals
Pr_HSPACE(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
PSPACE^cc : Communication Complexity PSPACE
PSPACE/poly : PSPACE With Polynomial-Size Advice
PT₁ : 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
QAC⁰ : Quantum AC⁰
QAC⁰[m] : Quantum AC⁰[m]
QACC⁰ : Quantum ACC⁰
QAC_f⁰ : QAC⁰ 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
QMA₁ : One Sided QMA
QMA_log : 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
QMIP_le : Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement
QMIP_ne : Quantum Multi-Prover Interactive Proofs With No Prior Entanglement
QNC : Quantum NC
QNC⁰ : Quantum NC⁰
QNC⁰/qpoly : Quantum NC⁰ With Polynomial-Size Quantum Advice
QNC⁰/🐱 : Quantum NC⁰ With Polynomial-Size Quantum Advice
QNC_f⁰ : Quantum NC⁰ With Unbounded Fanout
QNC¹ : Quantum NC¹
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
R_HL : Randomized Halting Logarithmic-Space
R_HSPACE(f(n)) : One-Sided Error Halting Probabilistic f(n)-Space
RL : Randomized Logarithmic-Space
RNC : Randomized NC
RNC¹ : Randomized NC1
RP : Randomized Polynomial-Time
RP^cc : Communication Complexity RP
RP_{$k {\displaystyle k}$}^cc : Randomized P_{$k {\displaystyle k}$}^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
S₂P : Second Level of the Symmetric Hierarchy
S₂E : Second Level of the Symmetric Linear Exponent Hierarchy
S₂-EXP•P^NP : Don't Ask
SAC : Semi-Unbounded-Fanin AC
SAC⁰ : Semi-Unbounded-Fanin AC⁰
SAC¹ : Semi-Unbounded-Fanin AC¹
SAPTIME : Stochastic Alternating Polynomial-Time
SBP : Small Bounded-Error Probability
SBP^cc : 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
SF_k : Width-k Bottleneck Turing Machines
Σ₂P : 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[ $t(n)$ ] : 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
StoqMA : Stoquastic MA
SUBEXP : Deterministic Subexponential-Time
symP : Alternate Name for S₂P
SZK : Statistical Zero Knowledge
SZK_h : SZK With Limited Help

T

TALLY : Tally Languages
TC : Threshold Circuits
TC⁰ : Constant-Depth Threshold Circuits
TC⁰(FOLL) : Languages that are TC⁰ Turing reducible to FOLL
TC¹ : Log-depth Threshold Circuits
TFNP : Total Function NP
Θ₂P : Alternate name for P^NP[log]
TI : Tensor Isomorphism
TOWER : Iterated Exponential Time
TreeBQP : BQP Restricted To Tree States
TREE-REGULAR : Regular Tree-Valued Languages

U

UAM^cc : 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
UP^cc : Communication Complexity UP
UPostBPP^cc : Unrestricted Communication Analogue of PostBPP
UPP^cc : Unrestricted Communication Analogue of PP
US : Unique Polynomial-Time
USBP^cc : Unrestricted Communication Analogue of SBP
UWAPP^cc : Unrestricted Communication Analogue of WAPP

V

VC_k : Verification Class With A Circuit of Depth K
VC_or : Verification Class With OR
VNC_k : Valiant NC Over Field k
VNP_k : Valiant NP Over Field k
VP_k : Valiant P Over Field k
VPL : Visibly pushdown languages
VQP_k : Valiant QP Over Field k

W

W[1] : Weighted Analogue of NP
WAPP : Weak Almost-Wide PP
WAPP^cc : 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
XP_uniform : 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

ZAM^cc : 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
ZPP^cc : Communication Complexity ZPP
ZPTIME(f(n)) : Zero-Error Probabilistic f(n)-Time
ZQP : Zero-Error Extension Of EQP