quantumchina的个人博客分享 http://blog.sciencenet.cn/u/quantumchina

博文

[转载]复杂度类集Complexity Zoo

已有 264 次阅读 2019-8-20 11:11 |个人分类:数学|系统分类:科研笔记| 计算, 数学, 计算机 |文章来源:转载

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

目前共有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-NPC - 1NAuxPDAp - 2-EXP - 3SUM-hard - #AC0 - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕Pcc - ⊕SAC0 - ⊕SAC1

A

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

B

βP - BC=P - BH - BPd(P) - BPE - BPEE - BPHSPACE(f(n)) - BPL - BP•NP - BPP - BPPcc - BPPkcc - 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

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

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

E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - ELkP - EP - EPTAS - k-EQBP - EQP - EQPK - 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(t(n)) - FOLL - FP - FPNP[log] - FPL - FPR - FPRAS - FPT - FPTnu - FPTsu - FPTAS -FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G

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

H

HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME\delta(f(n)) - HeurP - HeurPP - HeurNTIME\delta(f(n)) - HkP - HVSZK

I

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

L

L - LC0 - LH - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP

M

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

N

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 - NPkcc - 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))

O

OptP

P

P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pkcc - 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 - PKPKC - 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

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

R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - RHL - RHSPACE(f(n)) - RL - RNC - RP - RPcc - RPkcc - RPP - RQP - RSPACE(f(n))

S

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[t(n)] - SPspan-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZKh

T

TALLY - TC0 - TFNP - Θ2P - TI - TreeBQP - TREE-REGULAR

U

UAMcc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UPcc - UPostBPPcc - UPPcc - US - USBPcc - UWAPPcc

V

VCk - VCOR - VNCk - VNPk - VPk - VPL - VQPk

W

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

X

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

Y

YACC - YP - YPP - YQP

Z

ZAMcc - ZBQP - ZK - ZPE - ZPP - ZPPcc - ZPTIME(f(n)) - ZQP


参考来源:

https://complexityzoo.uwaterloo.ca/Complexity_Zoo



http://blog.sciencenet.cn/blog-3364677-1194390.html

上一篇:指数阶乘
下一篇:量子世界的波粒二象性

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-9-23 21:55

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部