计算复杂性理论（一）

计算复杂性理论是理论计算机科学的一个子领域，其主要目标之一是分类和比较解决有限组合对象问题的实际难度 - 例如，给定两个自然数 n 和 m，它们是互质的吗？给定一个命题公式 ϕ，它是否有令人满意的分配？如果我们要在大小为 n×n 的棋盘上下棋，白方从给定的初始位置是否有获胜策略？从经典可计算性理论的角度来看，这些问题同样困难，因为它们都是有效可判定的。但它们在实际难度上似乎仍然存在很大差异。对于给定的一对数字 m＞n＞0，我们可以通过一种方法（欧几里得算法）确定它们的相对素数，该方法需要与 log(n) 成比例的步骤数。另一方面，解决后两个问题的所有已知方法都需要在一大类案例中进行“强力”搜索，而这些案例的数量至少会随问题实例的规模呈指数增长。

复杂性理论试图通过提出一个正式标准来精确区分这些区别，该标准定义数学问题是否可行可判定——即它可以用传统的图灵机以与其输入大小的多项式函数成比例的步骤数来解决。具有此属性的问题类称为 P （或多项式时间），包括上述三个问题中的第一个。可以正式证明 P 不同于某些其他类别，例如 EXP （或指数时间），其中包括上面的第三个问题。上述第二个问题属于称为 NP（非确定性多项式时间）的复杂性类别，包括那些可以通过非确定性图灵机的某些计算正确解决的问题，这些计算步骤是其输入大小的多项式函数。一个著名的猜想——通常被认为是整个理论计算机科学中最基本的猜想——指出 P 也正确地包含在 NP 中——即 P⊊NP。

证明这些和其他复杂性类别的不一致仍然是复杂性理论中重要的未决问题。但即使在目前的发展状态下，这个主题也以一种与我们对这些主题的知识的性质和范围有关的方式将逻辑、数学和周边领域的许多主题联系起来。因此，对复杂性理论基础的反思不仅对计算机科学哲学具有潜在意义，而且对数学哲学和认识论也具有潜在意义。

1. 关于计算复杂性

1.1 初步示例

1.2 基本约定

1.3 区分复杂性概念

2. 复杂性理论的起源

2.1 丘奇论题和有效可计算性

2.2 科巴姆-埃德蒙论题和可行可计算性

3. 技术发展

3.1 确定性和非确定性计算模型

3.2 复杂性类别和层次定理

3.3 归约和 NP-完备性

3.4 其他复杂性类别

3.4.1 NP 和 coNP

3.4.2 多项式层次、多项式空间和指数时间

3.4.3 并行、概率和量子复杂性

4. 与逻辑和哲学的联系

4.1 关于 P≠NP 的意义？

4.2 可满足性、有效性和模型检查

4.3 证明复杂性

4.4 描述复杂性

4.5 有界算术

4.6 严格有限主义

4.7 逻辑知识和演绎推理的复杂性

5. 进一步阅读

参考书目

学术工具

其他互联网资源

相关条目

1. 关于计算复杂性

计算复杂性理论发展的核心是决策问题的概念。这样的问题对应于我们希望决定其成员资格的集合 X。例如，问题 PRIMES 对应于素数的自然数子集 - 即 {n∈N∣n 为素数}。决策问题通常以关于一类数学对象的问题的形式指定，其正实例决定了所讨论的集合 - 例如

SAT  给定一个命题逻辑公式φ，是否存在一个令人满意的φ分配？

旅行商（TSP）  给定一个城市列表V，每对城市u，v∈V之间的整数距离d（u，v）以及预算b∈N，是否存在一个访问每个城市一次并返回总距离≤b的出发城市的旅行？

整数规划  给定一个n×m整数矩阵A和一个n维整数向量→b，是否存在一个m维整数向量→x使得A→x = b？

完美匹配  给定一个有限二分图G，G中是否存在完美匹配？ （如果 G 的顶点可以分成两个不相交的集合 U 和 V，并且它的所有边 E 将 U 中的顶点连接到 V 中的顶点，则 G 是二分的。匹配是边 M⊆E 的子集，其中没有两个成员共享一个公共顶点。如果 M 匹配所有顶点，则 M 是完美的。）

这些问题在两个基本方面是复杂性理论中研究问题的典型。首先，它们都是可有效判定的。这就是说，它们都可以在可计算性理论中研究的“原则上”的意义上得到判定——即通过一个对所有输入都在有限步中停止的有效程序。其次，在它们出现的情况下，我们不仅有兴趣解决问题的孤立实例，而且有兴趣开发允许大规模有效解决问题的方法——即针对我们可能实际关注的所有实例。这种兴趣通常源于计算问题与实际任务的关系，我们试图使用离散数学方法来分析这些实际任务。例如，当我们希望检查一组规范的一致性时，就会出现 SAT 实例（例如，在安排会议会议或设计电路板时可能出现的规范）；在许多物流和规划应用中，就会出现 TSP 和整数规划的实例；当我们希望找到将候选人与工作配对的最佳方法时，就会出现完美匹配的实例，等等。[1]

执行算法以解决问题实例所涉及的资源通常可以根据返回解决方案所需的处理器周期数（即基本计算步骤）和内存空间量（即辅助计算的存储空间）来衡量。复杂性理论的方法不仅有助于决定我们如何最有效地利用这些资源，而且还有助于我们区分哪些有效可判定问题首先具有有效的决策方法。在这方面，传统上在理论之前就区分可行可判定问题（即那些在实践中可以通过有效算法解决的问题）和难解问题（即那些缺乏此类算法的问题，因此可能被视为本质上难以判定的问题（尽管原则上可能是可判定的）。通过考虑一些额外的例子，最容易理解这种区别的重要性。

1.1 初步示例

计算问题的一个熟悉的例子是素数测试，即确定 n∈PRIMES？早在数字计算机发展之前，这个问题就在数学中得到了深入研究。 （例如，请参阅（Williams 1998）了解素数测试的历史，以及（Crandall and Pomerance 2005）了解最新的最新研究成果。）在 19 世纪和 20 世纪出现许多初步成果之后，PRIMES 问题在 2004 年被证明具有所谓的多项式时间决策算法，即所谓的 AKS 素数测试（Agrawal、Kayal 和 Saxena 2004）。这使 PRIMES 相对于现在在复杂性理论和算法分析中被广泛接受的标准而言是可判定的（参见第 2.2 节）。

两个相关问题可用于说明复杂性理论家试图分析的难度对比：

相对素数给定自然数 x 和 y，x 和 y 是否具有最大公约数 1？（即 x 和 y 是否互质？）

因式分解给定自然数 x 和 y，是否存在 1＜d≤y 使得 d∣x？

相对素数可以通过应用欧几里得最大公约数算法来解决 - 即在输入 y≤x 时，重复计算余数 r0=rem(x,y)、r1=rem(y,r0)、r2=rem(r0,r1)……，直到 ri=0，然后如果 ri−1=1，则返回“是”，否则返回“否”。可以证明，该序列中的步数始终小于或等于 5⋅log10(x)。[2] 这意味着，为了确定 x 和 y 是否互质，只需计算与两个数中较小数的十进制表示中的位数成比例的余数。由于这也可以通过高效算法（例如长除法）来实现，因此可以合理地认为，如果我们能够写下一对数字 x,y——例如，将它们的数值表示以二进制或十进制形式写在黑板上，或将这些数字存储在当前设计的数字计算机的内存中——那么我们或这样的计算机也将能够执行这些算法来判断 x 和 y 是否互质。这是可行可判定问题的标志——即可以在日常具体体现的计算的“实践”意义上判定的问题。

因式分解是寻找给定数字 x 的素数分解的常见问题的决策变体——即素数 pi 和指数 ai 的唯一序列，使得 x=pa11⋅…⋅pakk。不难看出，如果存在一种有效的算法来判定因式分解，那么也存在一种有效的算法来确定素数分解。[3] 还很容易看出，将 x 进行素数分解的函数在传统意义上的可计算性理论中是有效可计算的。例如，它可以通过试除法算法计算出来。

试除法最简单的形式是依次测试 x 是否能被每个小于 x 的整数整除，并记录迄今为止找到的除数。由于此过程所需的除法次数与 x 本身成正比，因此乍一看，用纸笔计算用此方法分解中等大小的数（比如 x＜100000）并不是一项特别繁重的任务。但请注意，我们通常使用位置符号（如二进制或十进制数字）表示自然数。这样做的结果是，通常作为数值算法的输入来表示输入 x∈N 的表达式的长度不是与 x 本身成正比，而是与 logb(x) 成正比，其中 b≥2 是所讨论的符号系统的基数。[4] 因此，可以具体地刻写表示天文数字的中等长度的位置数字。例如，一个 60 位二进制数表示的数字大于以秒为单位估计的宇宙年龄，而一个 250 位二进制数表示的数字大于以普朗克时间估计的宇宙年龄。[5]

因此，有些自然数我们可以轻松地用二进制表示出来，但没有人类数学家或可预见的计算设备可以执行试除法算法。这似乎也不是特别令人不安，因为这种算法确实是“幼稚的”，因为它允许进行一些明显的改进——例如，我们只需要测试 x 是否能被数字 2,…,√x 整除就能找到初始因子，其中我们只需要测试那些本身是素数的因子（其中有限多个可以存储在查找表中）。尽管如此，几百年来，数学家们一直在尝试寻找更有效的因式分解方法。迄今为止开发的最有效的因式分解算法与试除法算法类似，因为它需要许多原始步骤，这些步骤的数量大致与 x（即其输入的大小，而不是其二进制表示的长度）成比例增长。[6]这些观察的结果是，存在具体可记数的数字——比如说大约 400 位十进制数字——具有以下属性：(i) 我们目前不知道它们的因式分解；(ii) 即使我们能够使用我们想要的任何组合的当前可用计算设备和算法，我们也极不可能找到它们。

与上面介绍的问题一样，因式分解具有相当大的实际重要性，也许最著名的原因是众所周知的加密协议的安全性假设它在一般情况下是难以解决的（例如，参见 Cormen、Leiserson 和 Rivest 2005）。但上述观察仍然不会对我们了解数字的质因数分解的能力造成任何根本限制。因为我们仍然希望进一步的研究将产生一种更有效的算法，使我们能够确定我们可能实际感兴趣的每个数字 x 的质因数分解。欧几里得算法与试除法的比较再次为描述我们可能期望这种算法具有的属性提供了有用的背景。请注意，先前的观察表明，我们不应该用 x 本身来衡量数值算法的输入 x∈N 的大小，而应该用 x 的二进制表示的长度来衡量。如果我们让 |x|=dflog2(x) 表示这个量，那么很容易看出，欧几里得算法的效率由一个与 |x|c1 成比例增长的函数给出，其中 c1 是固定的（事实上，c1=1），而试除法的效率由一个与 c2 成比例的函数 c|x|2 给出，其中 c2 是固定的（事实上，c2=2）。

这些函数增长率的差异说明了多项式时间复杂度（目前被复杂性理论家视为可行性的试金石）与指数时间复杂度（传统上被视为难解性的试金石）之间的对比。例如，如果可以证明不存在多项式时间分解算法，那么得出因式分解是一个真正难解问题的结论似乎是合理的。

虽然目前尚不清楚是否如此，但当代结果提供了间接证据表明因式分解确实是难解的（见第 3.4.1 节）。可以为猜想 SAT、TSP 和整数规划的难解性提供更有力的证据（以及逻辑、图论、线性代数、形式语言理论、博弈论和组合学等学科中许多其他具有实际意义的问题的难解性）。复杂性理论的技术发展旨在使这种计算难度的比较更加精确，并表明将某些问题归类为难解问题可以通过严格的数学分析来解决。

1.2 基本惯例

正如我们刚刚看到的，在计算复杂性理论中，问题 X 的复杂度与执行最有效的算法的难度成正比。类似地，如果问题 Y 拥有比决定 X 的最有效算法更有效的决策算法，则问题 X 被认为比另一个问题 Y 更复杂（或更难）。为了使这些定义更加精确，采用了许多技术惯例，其中许多是从可计算性理论（例如 Rogers 1987）和算法分析（例如 Cormen、Leiserson 和 Rivest 2005）的相邻领域借用的。在继续讨论之前，总结一下这些惯例将很有用。

选择计算参考模型 M 来表示算法。假设 M 是一个合理模型，因为它准确反映了执行数学实践中遇到的非正式指定算法的计算成本。传统上选择确定性图灵机模型 T 来实现此目的。（有关合理模型的进一步讨论以及此选择的理由，请参阅第 2.2 节。）

决策问题表示为由可作为机器 M∈M 的输入的对象组成的集合。例如，如果使用 T 作为参考模型，则假设所有问题 X 都表示为有限二进制字符串集 - 即 X⊆{0,1}∗。这是通过定义映射 ⌜⋅⌝:X→{0,1}∗ 来实现的，该映射的定义取决于组成 X 的对象的类型。例如，如果 X⊆N，则 ⌜n⌝ 通常为表示 n 的二进制数字。如果 X 是 FormL 的子集（即形式语言 L（例如命题逻辑）上的公式集），则 ⌜ϕ⌝ 通常为 ϕ 的 (二进制) 哥德尔数。基于这些约定，问题 X 今后将通过对应于此类编码下的图像的字符串集 {⌜x⌝:x∈X}⊆{0,1}∗（通常称为语言）来识别。

仅当机器 M 相对于模型 M 的标准输入输出约定计算出 X 的特征函数时，才可以说机器 M 判定语言 X。例如，仅当对于所有 x∈{0,1}∗，将 T 应用于 x 的结果会产生一个停止计算，如果 x∈X，则结束于指定的接受状态，如果 x∉X，则结束于指定的拒绝状态。函数问题是计算给定函数 f:A→B 的值的问题。如果 M 的操作引起的映射与 f(x) 一致，则称 M 能够解决函数问题 f:A→B，即，如果对于所有 x∈A，M(x)=f(x)，其中 M(x) 表示将机器 M 应用于输入 x 的结果，同样相对于模型 M 的输入输出约定。

对于每个问题 X，还假设为其实例定义了适当的问题大小概念。正式地，这是一个函数 |⋅|:X→N，选择该函数是为了使 X 的决策算法的效率在 |x| 中均匀变化。如我们所见，如果 X⊆N，则标准做法是取 |n|=log2(n)，即表示 n 的二进制数字 ⌜n⌝ 的位数（或长度）。类似地，如果 X 是语言 L 上的一类逻辑公式（例如命题逻辑或一阶逻辑），则 |ϕ| 通常是 ϕ 句法复杂性的度量（例如它包含的命题变量或从句的数量）。如果 X 是一个图论问题，它的实例将由形式为 G=⟨V,E⟩ 的有限图的编码组成，其中 V 是一组顶点，E⊆V×V 是一组边。在这种情况下 |G|通常是集合 V 和 E 基数的函数。

机器 M 的效率以其时间复杂度来衡量 - 即 M 停止并返回输入 x 的输出所需的基本步骤数 timeM(x)（其中“基本步骤”的精确概念将随模型 M 而变化）。通过考虑 tM(n)=max{timeM(x):|x|=n}，可以将该度量转换为 N→N 类型的函数 - 即 M 的最坏情况时间复杂度，定义为 M 停止并返回所有大小为 n 的输入 x 的输出所需的最大基本步骤数。 M 的最坏情况空间复杂度（表示为 sM(n)）定义类似，即对于所有大小为 n 的输入，在 M 的计算过程中访问或写入的磁带单元（或其他形式的内存位置）的最大数量。

根据两台机器的时间和空间复杂度的增长顺序来比较它们的效率。 具体而言，给定一个函数 f:N→N，我们将其增长顺序定义为 O(f(n))={g(n):∃c∃n0∀n≥n0(g(n)＜c⋅f(n))}，即所有渐近受 f(n) 限制的函数的集合，忽略标量因子。例如，对于所有固定的 k,c1,c2 ∈N，以下函数的时间复杂度均为 O(n2)：常数 k 函数 log(n),n,c1⋅n2+c2。但是 11000n3∉O(n2)。如果 tM1(n)∈O(tM2(n))，则称机器 M1 的时间复杂度较低（或运行速度比）另一台机器 M2 更快，反之则不然。机器之间的空间复杂度比较以类似的方式进行。

问题 X 的时间和空间复杂度是用判定 X 的渐近最有效算法的最坏情况时间和空间复杂度来衡量的。具体来说，如果时间最有效的机器 M 判定 X 的最坏情况时间复杂度为 O(t(n))，则我们说 X 的时间复杂度为 O(t(n))。类似地，如果 X 的时间复杂度渐近地受 Y 的时间复杂度限制，则说 Y 比 X 更难判定（或更复杂）。问题的空间复杂度定义类似。

现在可以将复杂性类定义为存在具有给定运行时间或运行空间复杂度的决策程序的问题集。例如，类 TIME(f(n)) 表示时间复杂度为 f(n) 的问题类。 P——或多项式时间——用于表示关于参考模型 T 的 k∈N 类 TIME(nk) 的并集。因此，P 包含所有存在决策算法的问题，该算法可以由时间复杂度为多项式增长级的图灵机实现。SPACE(f(n)) 和 PSPACE——或多项式空间——定义类似。我们将在下面考虑的其他几个复杂性类（例如 NP、BPP、BQP）是通过改变计算的参考模型、机器接受或拒绝输入或两者的定义来定义的。