561
个编辑
更改
跳到导航
跳到搜索
第901行：
第901行： − + 第917行：
第917行： − + − −
→Important complexity classes重要的复杂性类
The logarithmic-space classes (necessarily) do not take into account the space needed to represent the problem.
The logarithmic-space classes (necessarily) do not take into account the space needed to represent the problem.
对数空间类(必须)没有考虑表示问题所需的空间。
对数空间类(必要地)没有考虑表示问题所需的空间。
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using Boolean circuits; and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.
其他重要的复杂性类别包括 BPP、 ZPP 和 RP，它们使用概率图灵机定义; AC 和 NC，它们使用布尔电路定义; BQP 和 QMA，它们使用量子图灵机定义。# p 是计数问题(不是决策问题)的一个重要的复杂类。类如 IP 和 AM 使用交互式证明系统定义。ALL 是所有决策问题的类别。
其他重要的复杂性类别包括 BPP、 ZPP 和 RP，它们使用'''<font color="#ff8000"> 概率图灵机</font>'''定义; AC 和 NC，它们使用'''<font color="#ff8000"> 布尔电路</font>'''定义; BQP 和 QMA，它们使用'''<font color="#ff8000"> 量子图灵机</font>'''定义。# p 是计数问题(不是决策问题)的一个重要的复杂类。类如 IP 和 AM 使用交互式证明系统定义。ALL 是所有决策问题的类别。
===Hierarchy theorems层次定理===
===Hierarchy theorems层次定理===