ALL (複雜度) 此條目没有列出任何参考或来源。 (2011年3月21日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 在可計算性問題和計算複雜度理論裡面,ALL這個複雜度類代表所有的決定性問題(decision problem)的集合。 與其他複雜度類關係[编辑] ALL 包含了所有決定型問題的複雜度類,因此也包含了RE和co-RE。 外部連結[编辑] Complexity Zoo: Class ALL 查论编重要的複雜度類(完整列表)易解复杂度类对数空间相关 DLOGTIME AC0(英语:AC0) ACC0(英语:ACC0) TC0(英语:TC0) L · FL · SL · NL NC SC PolyL 多项式空间相关 P(P-完全) FP(英语:FP (complexity)) ZPP RP BPP BQP(QMA(英语:QMA) PostBQP(英语:PostBQP) EQP(英语:EQP)) 怀疑难解复杂度类 UP NP(NP完全 NP困难 反NP 反NP完全(英语:co-NP-complete)) FNP(英语:FNP (complexity))(TFNP(英语:TFNP (complexity))) PH PP #P(#P-完全(英语:Sharp-P-complete)) PSPACE(PSPACE完全(英语:PSPACE-complete)) 难解复杂度类 EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL 复杂度类的谱系 多項式譜系 指數譜系 Grzegorczyk谱系(英语:Grzegorczyk hierarchy) 算术谱系 相关复杂度族 DTIME NTIME DSPACE(英语:DSPACE) NSPACE 可能性核对证明(英语:Probabilistically checkable proof) 交互式证明系统 量子复杂性理论