计算复杂性理论（五）
这一观察结果部分解释了为什么目前预计开放问题 3a 的答案是肯定的。因为我们现在可以看到，对于某个 k，断言 PH=ΣPk 等同于断言确定验证者是否有 n 轮验证游戏的制胜策略的问题并不比对于所有 n≥k 的 k 轮游戏决定这个问题的问题更难。相关的观察与开放问题 3b 的状态有关。请注意，如果 PH=PSPACE，则双人 SAT 对于 PH 将是完整的（对于 PSPACE 也是如此）。由于 PH 定义为 ⋃k∈NΣPk，因此可以得出，对于某个 k，TWO PLAYER SAT∈ΣPk。但在这种情况下，我们再次面临这样的问题：确定验证者是否有 n 轮验证游戏的获胜策略，其难度并不比确定所有 n≥k 的 k 轮游戏的获胜策略更难。由于这再次与预期相反，人们普遍认为，不仅 PH⊊PSPACE，而且前者与后者的不同之处在于没有完整的问题。
3.4.3 并行、概率和量子复杂性
即使考虑到我们目前无法解决开放问题 1-3，图 2 中从 P 到 EXP 的复杂性类别层次结构也代表了目前可用的最强大的计算难度基准。除了这个层次结构之外，我们还研究了大量额外的类别，这些类别被认为划定了 P 内部或 P 与 NP 之间的额外结构。全面考虑这些类别的多样性超出了当前调查的范围。但为了补充我们对相对于 T 和 N 定义的类别的理解，考虑三个额外的类别——NC、BPP 和 BQP——将是有用的，它们是相对于其他计算模型定义的。
定义 NC 的一种方法是根据称为并行 RAM（或 PRAM）机器的计算模型 P。该模型是第 2.2 节中描述的传统 RAM 模型的变体，它允许并行性。PRAM 机器 P 由一系列程序 Π1,…,Πq(n) 组成，每个程序由一个有限的指令序列组成，用于像以前一样对寄存器执行操作。每个程序还控制一个带有自己的程序计数器和累加器的单独处理器。处理器并行操作，可以写入公共寄存器块，采用某种策略解决冲突。最后，组成 P 的程序数量（以及处理器数量）不是固定的，而是可以根据函数 q(n) 随输入 n 的大小而变化。这样，PRAM 机器可以招募更多处理器来处理更大的输入，尽管所采用的处理器数量必须在输入大小上均匀固定。
虽然 PRAM 模型是确定性的，但很容易看出，通过招募足够多的处理器来并行执行给定 N 的计算树中的所有路径，它的成员可用于有效地模拟非确定性图灵机 N 的操作。因此，该模型是 van Emde Boas (1990) 第二机器类的成员，因此不被认为是一个合理的计算模型。尽管如此，P 是一个有用的理论模型，因为它提供了一种正式的媒介来实现需要同时并行执行某些操作的程序。
人们早就知道，某些问题（例如矩阵乘法、图可达性和排序）允许并行算法，在某些情况下，这些算法比最有效的已知顺序算法更快（例如，参见 Papadimitriou 1994）。 但是，如果所讨论的算法实现这种加速的代价是必须使用相对于其输入大小呈指数级增长的处理器，那么这种观察结果仍然没有多大的实际意义。 因为在这种情况下，我们似乎不太可能构建一个可以具体实现它们的计算设备。
然而，值得注意的是，刚刚提到的问题的并行算法只需要输入 n 大小为多项式的处理器数量，也只需要 n 的多项对数时间（即，对于固定的 k，O(logk(n))）。这促使我们将 NC 定义为可由 PRAM 机器在 O(logc(n)) 时间内使用 O(nk) 个处理器（对于固定的 c,k∈N）解决的问题类。[31] 具体来说，满足此定义的机器执行的工作量（定义为每个处理器所需的步骤数之和）将是其输入大小的多项式。
我们已经看到，Cobham-Edmond 论文表明 P 与可通过相对于顺序计算模型（如 T）可实现的算法可行解决的问题类相吻合。同样，人们经常认为 NC 与可通过相对于并行模型（如 P）可实现的算法可行解决的问题类相吻合（例如，参见 Greenlaw、Hoover 和 Ruzzo 1995）。具体来说，可以证明，任何使用 O(nk) 个处理器在时间 O(logc(n)) 内运行的 PRAM 机器都可以用多项式时间顺序机器模拟。由此可知，NC 是 P 的一个子集。
NC 之所以引起人们的兴趣，部分原因是相反的包含关系未知 - 即以下问题也悬而未决：
开放问题 4 NC 是否正确包含在 P 中？
目前的共识是，与开放问题 1-3 一样，开放问题 4 也将得到肯定的回答。在这种情况下，启发式论证源于以下观察：如果 NC=P，那么每个拥有 O(nj) 顺序算法的问题 X 都可以“加速”，即允许使用并行算法，该算法只需要时间 O(logc(n)) 使用 O(nk) 处理器。即使考虑到 k 远大于 j 的情况，这种情况也被认为不太可能发生，因为 P 中的某些问题似乎具有“固有顺序性”，即表现出使其难以并行化的结构。具体来说，据推测，对于 P 完全问题而言，情况确实如此，例如确定布尔电路的计算结果是否为真，或者命题逻辑的 Horn 片段中的公式是否可满足。[32]
复杂性理论的另一个活跃研究领域涉及根据概率计算模型定义的类。假设此类模型的实例可以访问某些真正的随机源（例如公平硬币或量子力学随机数生成器），这些随机源可用于确定其计算过程。这一基本思想产生了许多用于建模概率计算的不同范例，其中最初的非确定性图灵机模型 N 是一个早期典范。然而，正如我们所见，非确定性图灵机不能用作概率计算的实用模型。因为为了使用 N 得出 x 不是给定语言 X 的成员的结论，我们需要检查 N 对此输入的所有潜在计算（这通常是不可行的）。
因此，我们也可以合理地问，我们如何修改 N 的定义，以获得可能有用地使用的概率算法的特征。一个答案体现在类 BPP 或有界误差概率多项式时间的定义中。[33] 此类最容易相对于称为概率图灵机 C 的计算模型来定义。这样的设备 C 可以访问随机数生成器，该生成器在其计算的每个步骤中都会产生一个新位，但其他方面与传统的图灵机类似。C 在下一步采取的操作由该位的值、其内部状态和当前扫描的符号决定。
现在可以将 BPP 定义为包括问题 X，使得存在一个概率图灵机 C∈C 和一个常数 12<p≤1，具有以下属性：
C 对所有输入都在多项式时间内运行；
对于所有输入 x∈X，至少有 p 个 C 在 x 上的可能计算被接受；
对于所有输入 x∉X，至少有 p 个 C 在 x 上的可能计算被拒绝。
该定义旨在将概率算法可判定问题的直观表征形式化为存在一个决策程序，该程序可以在计算过程中做出不确定的选择，但仍能在“绝大多数”情况下正确解决问题（即概率 p 不超过 12）。不难看出，如果我们拥有一个可由满足（i）-（iii）的机器 C 实现的判定 X 的算法，那么我们可以通过反复应用该算法并检查其大多数计算是被接受还是被拒绝，以任意高的概率正确判定 x∈X。[34]
由于标准图灵机模型 T 对应于 C 的一个特例，因此 P⊆BPP。长期以来，人们还认为 PRIMES 可能是属于 BPP 但不属于 P 的问题的一个例子。[35] 然而，我们现在知道，凭借 AKS 素数算法，这个问题属于 P 。目前，不仅已知的分离这些类别的候选者很少，而且不知道 NP 是否包含在 BPP 中（尽管 Lautemann (1983) 证明后者包含在 ΣP2 中）。因此，尽管在计算过程中做出随机选择的能力乍一看似乎合理，这使我们能够实际解决某些抵制有效确定性算法的问题，但这是否属实仍是一个悬而未决的问题。
近年来，最后一个复杂度类引起了广泛关注，称为 BQP（或有界误差量子多项式时间）。 BQP 的定义类似于 BPP，但使用量子计算模型 Q 而不是模型 C。这种模型可以粗略地描述为一种利用量子力学现象（如纠缠或干涉）对由量子位序列表示的数据执行操作的设备——即 0 和 1 矢量的量子叠加。基于 Manin (1980) 和 Feynman (1982) 的早期建议，20 世纪 80 年代和 90 年代提出了许多此类模型，BQP 的精确定义可以以此为基础——例如 Deutsch (1985) 的量子图灵机。
人们发现了几种可以在这种设备上实现的算法，这些算法比针对同一问题的最佳经典算法运行速度更快。其中包括用于搜索无序数据库的 Grover 算法 (Grover 1996)（运行时间为 O(n1/2)，而最佳经典算法为 O(n)）和用于整数分解的 Shor 算法 (Shor 1999)（运行时间为 O(log2(n)3)，而最著名的经典算法为 O(2log2(log2(n))1/3))。由于可以证明量子模型可以模拟经典图灵机等模型，因此 BQP 包含 P 和 BPP。正如我们刚刚看到的，BQP 至少包含一个问题 - 即分解 - 而不知道它是否包含在 P 中。
虽然可以证明 BQP⊆PSPACE，但前者与 NP 之间的关系目前尚不清楚。具体来说，目前还没有发现可以在更广泛接受的量子计算模型上实现的用于解决 NP 完全问题的多项式时间量子算法。关于是否有可能构建此类模型的物理实现，这些模型足够稳健，可以可靠地解决目前无法使用经典硬件解决的问题实例，也存在相当大的争议。即使找到了 P⊊BQP 的证明，也需要进一步的实证研究来确定量子计算对可行计算的极限或 Cobham-Edmonds 论文本身的地位的影响。尽管如此，量子计算目前是一个非常活跃的研究领域。[36]
4. 与逻辑和哲学的联系
迄今为止，哲学对计算复杂性理论的参与出奇地少。尽管有几个问题源于可计算性理论——例如尽管关于丘奇论题的地位和有效不可判定问题的意义等问题已经被广泛讨论，但关于科巴姆-埃德蒙兹论题和有效可判定但可行不可判定问题的意义等类似问题却很少引起数学哲学家的关注。尽管人们对逻辑知识和资源有限推理的兴趣持续存在，但认识论、决策理论和社会选择理论等领域最近才开始利用复杂性理论的概念和结果。本节将尝试通过强调计算复杂性与逻辑和哲学中的传统主题之间的联系来弥合其中的一些差距。
4.1 关于 P≠NP? 的意义
理论计算机科学之外对复杂性理论的欣赏很大程度上是由于 1-4 等开放性问题的知名度。其中，开放问题 1（以下简称 P≠NP?）引起了最大的关注。它与纯数学和应用数学中长期未解决的问题（例如黎曼猜想和霍奇猜想）一起，是一个重大奖项竞赛的主题——即千禧年难题 (Cook 2006)。它也经常是综述文章和流行论述的焦点——例如 (Sipser 1992)、(Fortnow 2009) 和 (Fortnow 2013)。
确实有几个理由让我们怀疑 P≠NP？的解决将会在计算机科学之外产生深远的实际和理论影响。也许其中最重要的理由围绕着这样一种可能性：尽管目前可以提供各种启发式论据来支持 P≠NP 的假设，但 P=NP 毕竟还是有可能为真。回想一下，P 可以被描述为可以有效判定成员资格的问题类，而 NP 可以被描述为一旦提供适当的证书就可以有效验证成员资格的问题类。如果事实证明 P=NP，那么对于所有 NP 问题，这两个任务的难度都会一致（最多为多项式因子）。由此产生的一些后果是，为命题公式 ϕ 找到令人满意的估值 v 并不比构建其真值表更难，对自然数进行因式分解并不比验证给定的因式分解是否正确更困难，等等。
我们的直觉强烈地反映了这样一个事实，即这类对中的前一个问题似乎比后者更难。但除了目前几乎不言而喻的区别被瓦解之外，P 和 NP 的巧合也会对我们目前在数学中面临的形势产生更根本的影响。假设 T 是一个递归公理理论，它足够强大到可以形式化我们目前的数学理论——例如具有选择公理 [ZFC] 的 Zermelo Fraenkel 集合论，并根据需要补充大基数假设。请注意，无论 T 的证明理论强度如何，以下关于该理论的可导性的问题仍然可能在多项式时间内可判定：
证明检查 T 给定 T 语言中的公式 ϕ 和适当类型的有限对象 D（例如，推导序列或树），D 是否是根据 T 的公理对 ϕ 的良好证明？[37]
对于这样的标准定义，对于每个 n，也将有 O(2n) 个 T 导数，长度 n=|D|（以 D 中的符号数来衡量）。因此，我们可以通过猜测长度为 n 的符号序列，然后检查（在多项式时间内）它是否是 ϕ 的良好证明，从而非确定性地检查 ϕ 是否可以通过大小 ≤n 的证明导出。因此，以下问题属于 NP：
n-PROVABILITYT 给定 T 语言中的公式 ϕ 和自然数 n，是否存在长度 ≤ n 的有效 T 导数 D，使得 D 是 ϕ 的有效证明？
当然，我们通常感兴趣的问题是，φ 是否可以在 T 中证明，而不受其导数长度的限制——例如，在φ 表达黎曼假设且 T 是像 ZFC 这样的理论的情况下。但在给冯·诺依曼的一封信中，哥德尔 (1956) 指出，如果我们能够有效地确定 n-PROVABILITYT，那么这对数学实践已经具有重大意义。请注意，似乎可以合理地假设没有一个人类数学家能够理解包含 1 亿个符号（≈25000 页）的证明。如果我们能够有效地检查 ϕ∈n-PROVABILITYT（假设 n=108）并得到否定的答案，哥德尔得出结论：“没有理由进一步思考 [ϕ]”（1956 年，第 612 页）。因为在这种情况下，证明 ϕ∉n-PROVABILITYT（对于足够大的 n 和足够强大的 T）就足以表明，即使存在 ϕ 的证明，我们也不可能理解它。
但现在请注意，由于 n-PROVABILITYT∈NP，如果碰巧 P=NP，那么通过可行长度的证明确定数学公式在我们首选的数学理论中是否可推导的任务将可以通过有效的算法来检查。哥德尔认为这将产生以下后果：
[D]尽管判定问题无法解决，但在是非问题的情况下，数学家的脑力劳动可以完全被机器取代。[38] （Gödel 1956, 612）
基于这一观察，一些最近的评论家（例如 Impagliazzo 1995、Arora 和 Barak 2009 和 Fortnow 2013）也强调了开放问题 1 的重要性，他们认为 P=NP 不仅在数学中，而且在许多其他任务中也需要创造力——例如理论构建或音乐创作——传统上认为涉及非算法洞察力的元素。
但是，尽管 P 和 NP 的巧合会产生有趣的后果，但发现一个验证 P≠NP 这一共识观点的证明似乎也应该被视为具有基础意义。正如我们所见，最常引用的支持将 P 正确纳入 NP 的证据是长期尝试寻找多项式时间算法解决 NP 问题失败，我们对这些问题有很强的实际兴趣，无论是在实践中决定还是证明其难以解决。[39] 因此，P≠NP 的证明不仅可以验证这种归纳证据，而且还可以提供额外的证据，证明科巴姆-埃德蒙兹论题对可行性的前理论概念进行了正确的分析。具体来说，它可以让我们无条件地断言 NP 难题在一般情况下是不可解决的。
但是，回想一下，这种归纳考虑只是可以引用来支持 P≠NP 的整体证据的一部分。 具体来说，各种启发式考虑也指出 NP 类和 coNP 类以及 PH 类和 PSPACE 类的不一致，因此对开放问题 2 和 3 给出了肯定的答案。 但如果 P=NP 的话，那么这些问题将以一种与我们目前的预期截然相反的方式得到否定解决（参见第 3.4.1 和 3.4.2 节）。
鉴于 P≠NP 这一猜想有几种非证明性证据形式的收敛，我们也有理由问，为什么这个命题在实践中如此难以解决。请注意，虽然这个命题起源于理论计算机科学，但它可以很容易地表述为关于自然数的陈述。具体来说，P≠NP 等价于以下命题：对于所有指标 e 和指数 k，存在一个命题公式 ϕ，使得确定性图灵机 Te 无法在|ϕ|k 步内正确确定 ϕ 在 SAT 中的成员资格。使用句法算术化中熟悉的技术，不难看出这个语句可以在一阶算术语言中形式化为 Π02 语句，即形式为 ∀x∃yψ(x,y) 的语句 Θ，其中 ψ(x,y) 仅包含有界数值量词。
仅基于其逻辑形式，我们目前不能排除 Θ 不仅独立于一阶皮亚诺算术 [PA]，而且独立于更强的公理系统（如 ZFC）的可能性。但是，尽管早期结果表明 P≠NP 可能独立于一些非常弱的公理理论（例如 DeMillo 和 Lipton 1980），但现在人们认为这个语句不太可能独立于像 PA 这样接近我们在实践中使用的数学公理的更强的理论。具体来说，Ben-David 和 Halevi (1992) 表明，如果可以使用当前的证明理论技术来证明 Θ 独立于 PA，那么这个证明本身也将表明 NP 非常接近于 P，而这种接近可以通过使用电路复杂性技术来精确实现。[40] 由于这被认为是难以置信的，Aaronson (2003) 认为，我们目前没有理由怀疑 P≠NP 比其他目前开放的数论陈述更有可能独立于 PA（更不用说 ZFC）。
但与此同时，人们也达成了共识，认为我们不太可能基于目前已知的证明方法来确定 P≠NP 的状态？一个熟悉的例子是对角化方法，正如在经典停机问题不可判定性的证明中所使用的那样（由此可以得出递归语言正确地包含在递归可枚举语言中）。我们已经看到，该方法的变体可用于在定理 3.1 的证明中显示 P⊊EXP。但是，产生这种分离的对角化证明通常在以下意义上相对于基于 oracle 的计算：如果这样的证明对于复杂度类 C1 和 C2 产生 C1≠C2，那么适当的修改通常也会对所有 oracle A⊆{0,1}∗ 产生 CA1≠CA2。[41] Baker、Gill 和 Solovay（1975）著名地建立了 oracle A 和 B 的存在，使得 PA=NPA 且 PB≠NPB。正如我们期望基于对角化的 P≠NP 证明与 A 和 B 相对化一样，这表明不可能使用此方法分离 P 和 NP。
尽管这个结果和其他结果通常被认为与 P≠NP？的状态有关，但解决这个问题和其他悬而未决的问题仍然是理论计算机科学研究的重要课题。最近，人们使用电路复杂性（例如 Razborov 和 Rudich 1994）、证明理论（例如 Buss 1999）和代数几何（例如 Mulmuley 和 Sohoni 2001）中的技术探索了几种分离复杂性类别的程序。然而，目前的共识（例如 Fortnow 2009）是这些方法仍然需要实质性的改进，或者需要真正的新方法才能产生所需的分离。
