||| |
计算领域的所有复杂度类集组成的空间
目前共有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
0-1-NPC - 1NAuxPDAp - 2-EXP - 3SUM-hard - #AC0 - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕Pcc - ⊕SAC0 - ⊕SAC1
A0PP - AC - AC0 - AC0[m] - AC1 - ACC0 - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AMcc - AMEXP - 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
βP - BC=P - BH - BPd(P) - BPE - BPEE - BPHSPACE(f(n)) - BPL - BP•NP - BPP - BPPcc - BPPcc - BPPKT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPPpath - 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 - BQPCTC - BQPtt/poly - BQTIME(f(n)) - k-BWBP
C=AC0 - C=L - C=P - CC - CC0 - CFL - CLOG - CH - Check - CL#P - CkP - CNP - coAM - coC=P - cofrIP - Coh - coMA - coModkP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPcc - coNP/poly - coNQP -coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ2 - CSIZE(f(n)) - CSL - CSP - CZK
D#P - DCFL - Δ2P - δ-BPP - δ-RP - DET - DiffAC0 - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC0
E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - ELkP - EP - EPTAS - k-EQBP - EQP - EQPK - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - EXP - EXP/poly - EXPSPACE
FBQP - FERT - FPERT - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO() - FOLL - FP - FPNP[log] - FPL - FPR - FPRAS - FPT - FPTnu - FPTsu - FPTAS -FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))
GA - GAN-SPACE(f(n)) - GapAC0 - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]
HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME(f(n)) - HeurP - HeurPP - HeurNTIME(f(n)) - HkP - HVSZK
IC[log,poly] - IP - IPP - IP[polylog]
L - LC0 - LH - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP
MA - MAcc - MA' - MAC0 - MAE - MAEXP - mAL - MAPOLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP0 - mcoNL - MinPB - MIP - MIP*[2,1] - MIPns - MIPEXP - (Mk)P - mL - MM - MMSNP - mNC1 - mNL - mNP - ModkL -ModL - ModkP - ModP - ModZkL - mP - MP - MPC - mP/poly - mTC0
NAuxPDAp - NC - NC0 - NC1 - NC2 - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZKh - NL - NL/poly - NLIN - NLO - NLOG - NONE - NNC(f(n)) - NP - NPC - NPC -NPcc - NPcc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMVt - NPMVt-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NPR - NPSPACE - NPSV - NPSV-sel - NPSVt - NPSVt-sel - NQP -NSPACE(f(n)) - NT - NT* - NTIME(f(n))
P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pcc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PHcc - Φ2P - PhP - Π2P - PINC - PIO - PK- PKC - PL - PL1 - PL∞ - PLF - PLL - PLS - PNP - PNPcc - P||NP - PNP[k] - PNP[log] - PNP[log^2] - P-OBDD - PODN - polyL - PostBPP - PostBPPcc - PostBQP - PP - PPcc - PP/poly - PPA - PPAD - PPADS - PPP - PPP -PPSPACE - PQMA[log] - PQUERY - PR - PR - PrHSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACEcc - PSPACE/poly - PT1 - PTAPE - PTAS -PT/WK(f(n),g(n)) - PZK
Q - QAC0 - QAC0[m] - QACC0 - QACf0 - QAM - QCFL - QCMA - QCPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA(2) - QMA1 - QMAlog - QMAM - QMA/qpoly - QMIP - QMIPle - QMIPne - QNC - QNC0 - QNCf0 -QNC1 - QP - QPH - QPLIN - QPSPACE - QRG - QRG(k) - QRG(2) - QRG(1) - QSZK
R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - RHL - RHSPACE(f(n)) - RL - RNC - RP - RPcc - RPcc - RPP - RQP - RSPACE(f(n))
S2P - S2-EXP•PNP - SAC - SAC0 - SAC1 - SAPTIME - SBP - SBPcc - SBQP - SC - SE - SEH - SelfNP - SFk - Σ2P - 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 - SZKh
TALLY - TC0 - TFNP - Θ2P - TI - TreeBQP - TREE-REGULAR
UAMcc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UPcc - UPostBPPcc - UPPcc - US - USBPcc - UWAPPcc
VCk - VCOR - VNCk - VNPk - VPk - VPL - VQPk
W[1] - WAPP - WAPPcc - WHILE - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t]
XOR-MIP*[2,1] - XL - XNL - XP - XPuniform
ZAMcc - ZBQP - ZK - ZPE - ZPP - ZPPcc - ZPTIME(f(n)) - ZQP
参考来源:
https://complexityzoo.uwaterloo.ca/Complexity_Zoo
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-23 13:59
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社