跳转到内容

ALL (复杂度)

维基百科，自由的百科全书

此条目没有列出任何参考或来源。 (2011年3月21日)
维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而被移除。

在可计算性问题和计算复杂度理论里面，ALL这个复杂度类代表所有的决定性问题(decision problem)的集合。

与其他复杂度类关系

ALL 包含了所有决定型问题的复杂度类，因此也包含了RE和co-RE。

外部链接

Complexity Zoo: Class ALL

重要的复杂度类（完整列表）

易解复杂度类

对数空间相关	DLOGTIME AC⁰（英语：AC0） ACC⁰（英语：ACC0） TC⁰（英语：TC0） L · FL · SL · NL NC SC PolyL

多项式空间相关	P（P-完全） FP（英语：FP (complexity)） ZPP RP BPP BQP（QMA（英语：QMA） PostBQP（英语：PostBQP） EQP（英语：EQP））

P、NP、反NP与PSPACE之间的关系

怀疑难解复杂度类

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））

难解复杂度类

复杂度类的谱系

相关复杂度族

DTIME
NTIME
DSPACE（英语：DSPACE）
NSPACE
可能性核对证明（英语：Probabilistically checkable proof）
交互式证明系统
量子复杂性理论

取自“https://zh.wikipedia.org/w/index.php?title=ALL_(複雜度)&oldid=37380454”

分类：

复杂度类

隐藏分类：

自2011年3月缺少来源的条目