计算领域的所有复杂度类集组成的空间

目前共有544复杂度类 

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

Symbols

0-1-NP_C - 1NAuxPDA^p - 2-EXP - 3SUM-hard - #AC⁰ - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕P^cc - ⊕SAC⁰ - ⊕SAC¹

A

A₀PP - AC - AC⁰ - AC⁰[m] - AC¹ - ACC⁰ - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AM^cc - AM_EXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APX -ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

B

βP - BC₌P - BH - BP_d(P) - BPE - BPEE - BP_HSPACE(f(n)) - BPL - BP•NP - BPP - BPP^cc - BPP^cc - BPP^KT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPP_path - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) -BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQP_CTC - BQP_tt/poly - BQTIME(f(n)) - k-BWBP

C

C₌AC⁰ - C₌L - C₌P - CC - CC⁰ - CFL - CLOG - CH - Check - CL#P - C_kP - CNP - coAM - coC₌P - cofrIP - Coh - coMA - coMod_kP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNP^cc - coNP/poly - coNQP -coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ₂ - CSIZE(f(n)) - CSL - CSP - CZK

D

D#P - DCFL - Δ₂P - δ-BPP - δ-RP - DET - DiffAC⁰ - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC⁰

E

E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - EL_kP - EP - EPTAS - k-EQBP - EQP - EQP_K - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - EXP - EXP/poly - EXPSPACE

F

FBQP - FERT - FPERT - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO() - FOLL - FP - FP^NP[log] - FPL - FPR - FPRAS - FPT - FPT_nu - FPT_su - FPTAS -FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G

GA - GAN-SPACE(f(n)) - GapAC⁰ - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

H

HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME(f(n)) - HeurP - HeurPP - HeurNTIME(f(n)) - H_kP - HVSZK

I

IC[log,poly] - IP - IPP - IP[polylog]

L

L - LC⁰ - LH - LIN - L_kP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP

M

MA - MA^cc - MA' - MAC⁰ - MA_E - MA_EXP - mAL - MA_POLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP₀ - mcoNL - MinPB - MIP - MIP*[2,1] - MIP^ns - MIP_EXP - (M_k)P - mL - MM - MMSNP - mNC¹ - mNL - mNP - Mod_kL -ModL - Mod_kP - ModP - ModZ_kL - mP - MP - MPC - mP/poly - mTC⁰

N

NAuxPDA^p - NC - NC⁰ - NC¹ - NC² - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZK_h - NL - NL/poly - NLIN - NLO - NLOG - NONE - NNC(f(n)) - NP - NPC - NP_C -NP^cc - NP^cc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMV_t - NPMV_t-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NP_R - NPSPACE - NPSV - NPSV-sel - NPSV_t - NPSV_t-sel - NQP -NSPACE(f(n)) - NT - NT* - NTIME(f(n))

O

OptP

P

P - P/log - P/poly - P^#P - P^#P[1] - P_CTC - PAC⁰ - PBP - k-PBP - P_C - P^cc - P^cc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PH^cc - Φ₂P - PhP - Π₂P - PINC - PIO - P^K- PKC - PL - PL₁ - PL_∞ - PLF - PLL - PLS - P^NP - P^NPcc - P^||NP - P^NP[k] - P^NP[log] - P^{NP[log^2]} - P-OBDD - PODN - polyL - PostBPP - PostBPP^cc - PostBQP - PP - PP^cc - PP/poly - PPA - PPAD - PPADS - P^PP - PPP -PPSPACE - P^QMA[log] - PQUERY - PR - P_R - Pr_HSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACE^cc - PSPACE/poly - PT₁ - PTAPE - PTAS -PT/WK(f(n),g(n)) - PZK

Q

Q - QAC⁰ - QAC⁰[m] - QACC⁰ - QAC_f⁰ - QAM - QCFL - QCMA - QCPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA(2) - QMA₁ - QMA_log - QMAM - QMA/qpoly - QMIP - QMIP_le - QMIP_ne - QNC - QNC⁰ - QNC_f⁰ -QNC¹ - QP - QPH - QPLIN - QPSPACE - QRG - QRG(k) - QRG(2) - QRG(1) - QSZK

R

R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - R_HL - R_HSPACE(f(n)) - RL - RNC - RP - RP^cc - RP^cc - RPP - RQP - RSPACE(f(n))

S

S₂P - S₂-EXP•P^NP - SAC - SAC⁰ - SAC¹ - SAPTIME - SBP - SBP^cc - SBQP - SC - SE - SEH - SelfNP - SF_k - Σ₂P - SKC - SL - SLICEWISE PSPACE - SNP - SO - SO(Horn) - SO(Krom) - SO(LFP) - SO(TC) - SO[] - SP- span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZK_h

T

TALLY - TC⁰ - TFNP - Θ₂P - TI - TreeBQP - TREE-REGULAR

U

UAM^cc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UP^cc - UPostBPP^cc - UPP^cc - US - USBP^cc - UWAPP^cc

V

VC_k - VC_OR - VNC_k - VNP_k - VP_k - VPL - VQP_k

W

W[1] - WAPP - WAPP^cc - WHILE - W[P] - WPP - W[SAT] - W[*] - W[t] - W^*[t]

X

XOR-MIP*[2,1] - XL - XNL - XP - XP_uniform

Y

YACC - YP - YPP - YQP

Z

ZAM^cc - ZBQP - ZK - ZPE - ZPP - ZPP^cc - ZPTIME(f(n)) - ZQP

参考来源：

https://complexityzoo.uwaterloo.ca/Complexity_Zoo