可计算性和复杂性（二）

但是，原始递归函数并不包括所有原则上可计算的函数。为了看到这一点，我们可以再次使用对角化。我们可以系统地编码所有元数为 1 的原始递归函数的定义，称它们为 p1、p2、p3 等等。

然后，我们可以构建一个图灵机来计算以下对角函数的值，D(n)=pn(n)+1。

请注意，D 是一个从 N 到 N 的完全可计算函数，但它不是原始递归函数。为什么？为了矛盾，假设 D 是原始递归函数。那么对于某个 d∈N，D 将等于 pd。但随后会得出

pd(d)=pd(d)+1，

这是一个矛盾。因此，D 不是原始递归函数。

唉，上述对角线论证适用于任何可以被视为所有可计算函数类候选的全函数类。如果我们希望所有函数在原则上而不仅仅是在实践中都是可计算的，那么解决这个问题的唯一方法是添加某种无界搜索操作。这就是哥德尔将原始递归函数扩展为递归函数所做的。

定义无界最小化算子 μ，如下所示。令 f 为元数为 k+1 的可能偏函数。则 μ[f] 定义为元数为 k 的以下函数。输入为 x1,…,xk 时执行以下操作：

对于 i=0 到 ∞ 执行 {

如果 f(i,x1,…,xk)=1，则输出 i

}

因此，如果 f(i,x1,…,xk)=1，且对于所有 j<i，f(j,x1,…,xk) 有定义但不等于 1，则 μ[f](x1,…,xk)=i。否则 μ[f](x1,…,xk) 未定义。

哥德尔将递归函数集定义为在组合、原始递归和 μ 下的初始原始递归函数的闭包。根据此定义，递归函数与 Lambda 演算、Kleene 形式系统、马尔可夫算法、Post 机器和图灵机可计算的部分函数集完全相同。

4. 计算复杂性：实践中的可计算函数

第二次世界大战期间，图灵帮助设计和制造了布莱切利园的 Bombe 专用计算设备。他使用 Bombe 破解了德国“Enigma”密码，为盟军提供了极大帮助 [Hodges，1992]。到 20 世纪 60 年代，计算机已在工业和大学中广泛使用。随着算法被开发用于解决无数问题，一些数学家和科学家开始根据算法的效率对其进行分类，并寻找针对某些问题的最佳算法。这是现代计算理论的开端。

在本节中，我们处理的是复杂性而不是可计算性，我们考虑的所有图灵机都会在其所有输入上停止运行。我们不会通过停止来接受，而是假设图灵机通过输出“1”来接受，通过输出“0”来拒绝，因此我们重新定义了总机器 M 所接受的集合，

L(M)={n∣M(n)=1}。

算法所花费的时间取决于输入和运行它的机器。复杂性理论中第一个重要的见解是，算法复杂性的一个很好的衡量标准是其渐近最坏情况复杂性与输入大小 n 的关系。

对于输入 w，让 n=|w| 表示 w 的长度。根据 [Hartmanis, 1989]，我们说，如果对于所有长度为 n 的 w，M(w) 最多需要 T(n) 步然后停止，则图灵机 M 的运行时间为 T(n)。这被称为最坏情况复杂度，因为 T(n) 必须与长度为 n 的任何输入所花费的时间一样大。

对于任何函数 T:N→N，让

TIME[T(n)]={A∣A=L(M)，其中某个 M 在时间 T(n) 内运行}。

Alan Cobham 和 Jack Edmonds 确定了复杂度类 P，即可在某个多项式时间内识别的问题，它是可行问题类的极好数学包装——这些问题的所有中等大小的实例都可以被可行地识别，

P=⋃i=1,2,…TIME[ni]

任何不在 P 中的问题肯定是不可行的。另一方面，具有 P 中算法的自然问题最终往往会发现实际上可行的算法。

除了 P 之外，还定义和研究了许多重要的复杂性类；其中一些是 NP、PSPACE 和 EXPTIME。 PSPACE 由那些可使用多项式量内存空间解决的问题组成。EXPTIME 是可在时间 2p(n) 内解决的多项式 p 问题集。

上述类别中最有趣的可能是 NP：非确定性多项式时间。该定义并非来自真实机器，而是数学抽象。非确定性图灵机 N 在每个步骤中从两个可能的操作中选择一个（猜测）。如果在输入 w 时，这些选择的某个序列导致接受，则我们说 N 接受 w，并且我们说 N 在输入 w 上所花费的非确定性时间只是导致接受的序列中采取的步骤数。非确定性机器不会为它可能做出的所有其他可能选择付费，而只会为正确选择的单个序列付费。

NP 有时被描述为具有简短成员证明的问题集 S。例如，假设我们给出了一个包含 m 个大自然数的列表：a1,…,am 和一个目标数字 t。这是子集和问题的一个实例：m 个数字中是否存在一个子集，其和恰好为 t？这个问题很容易在非确定性线性时间内解决：对于每个 i，我们猜测是否取 ai。接下来，我们将决定取的所有数字相加，如果和等于 t，则接受。因此，非确定性时间是线性的，即某个常数乘以输入的长度 n。但是，没有已知的（确定性的）方法可以在小于 n 的指数时间内解决这个问题。

4.1 约简和完备性

人们对算法进行了大量研究，许多重要问题的复杂性得到了很好的理解。具体来说，问题之间的约简已被定义并用于比较两个问题的相对难度。直观地，如果存在一个易于计算的转换τ，将 A 的实例映射到 B 的实例并保留成员资格，即τ(w)∈B⇔w∈A，则我们说 A 可约简为 B（A≤B）。

值得注意的是，很大一部分自然发生的计算问题对于上述类别之一而言是完整的。（如果 A 是 C 的成员，并且 C 中的所有其他问题 B 都不比 A 难，即 B≤A，则问题 A 对于复杂性类 C 是完整的。同一类的两个完整问题具有相同的复杂性。）

这种完备性现象的原因尚未得到充分解释。一个合理的解释是，自然计算问题往往具有图灵通用机意义上的通用性。某一复杂度类中的通用问题可以模拟该类中的任何其他问题。

1971 年，Cook 证明 SAT 是 NP 完全的 [Cook, 1971]。不久之后，Karp 证明许多重要的组合问题也是 NP 完全的，从而确立了 NP 类的重要性 [Karp, 1972]。

我们上面对归约的定义不够精确，只是说映射 τ 必须易于计算。Karp 使用的归约是多项式时间归约，即 τ 可以在多项式时间内计算。此后，许多研究人员发现，自然问题在令人惊讶的弱归约下，包括对数空间归约 [Jones, 1973]、一阶归约 [Immerman, 1999]、投影 [Valiant, 1982] 和一阶投影 [Immerman, 1999]，对于自然复杂性类别，自然问题仍然是完整的。

除了极少数例外，当一个自然问题属于 NP 时，它要么是 NP 完全的，要么是 P 完全的。人们想知道情况是否总是如此。Ladner 证明，如果 P ≠ NP，那么就有一个中间问题 I，它属于 NP，但不属于 P，也不是 NP 完全的 [Ladner, 1975]。

Ladner 的证明方法称为延迟对角化。他将自己的结果推广到：对于任何两个表现良好的复杂度类 C、E，其中 C 严格包含在 E 中，存在一个中间类 D，其中 C 严格包含在 D 中，D 严格包含在 E 中。因此，复杂度类的排序是密集的。

然而，这些中间问题往往不会出现。最近，这种现象通过 Feder 和 Vardi 的二分法猜想引起了广泛关注 [Feder and Vardi，1999]。Schaefer 用一篇富有洞察力的论文介绍了这项工作，他在论文中研究了布尔可满足性问题的所有变体 [Schaefer，1978]。他证明了每个这样的问题要么是 NP 完全的，要么是 P 中的，因此 Ladner 的中间问题不能出现在这样的可满足性问题中。由于只有这两种可能性，Schaefer 称之为二分法。

事实上，如果仔细观察，我们会发现所有 Schaefer 可满足性问题要么是 NP 完全的，要么是 P 完全的，要么是⊕L 完全的，要么是 NL 完全的，要么是 L 完全的，要么是平凡的 [Allender et al., 2009]。也就是说，P 中的非平凡问题可能是 P 完全的，或者对于 P 中的这三个复杂度类别之一来说是完全的。换句话说，如果我们仔细观察，NP/P 二分现象问题实际上是一种“多分”现象，即所有非平凡可满足性问题对于五个众所周知的复杂度类别之一都是完全的。

Feder 和 Vardi 研究了 Schaefer 二分法，并推测它适用于所有有限域约束满足问题 (CSP) [Feder and Vardi, 1999]。有限域 CSP C 由有限域 D 和 D 上的有限关系集 R1,…,Rk 组成。C 的一个实例由一组变量 v1,…vn 和一个原子的合取 φ≡⋀Ri(vj1,…) 组成。实例 φ 的答案为“是”，即 φ∈C 当且仅当将变量分配给域 D 的元素，使得 φ 得到满足。

对于大小为 2 的域，CSP 问题只是一个可满足性问题，因此 Schaefer 定理已经为这种情况建立了 Feder 和 Vardi 猜想。域大小为 3 的 CSP 的一个简单实例是无向图的 3COLOR 问题。给定这样的图 G，G 的顶点是否可以被染成三种颜色中的一种，使得没有两个相邻的顶点具有相同的颜色？要将其写成 CSP，让 D={R,Y,B} 为三种不同颜色的集合，让关系 N 为 D 上的不等关系。然后从 G=(V,E) 得到 3COLOR 的实例为φG=⋀(u,v)∈EN(u,v)。注意φG 表示每当 G 中的顶点 u 和 v 之间存在边时，u 和 v 就会被分配不同的颜色。

Feder 和 Vardi 的猜想导致了一项极其富有成效的研究计划。特别是，从 [Jeavons et al. 1997] 开始，许多论文发展了丰富的 CSP 代数理论；有关综述，请参阅 [Bulatov, 2018]。最终，通过应用和推进这一代数理论，Bulatov 和 Zhuk 独立证明了 Feder 和 Vardi 猜想 [Bulatov, 2017; Zhuk，2017]。

4.2 复杂性的重要性

NP 类之所以得到如此深入的研究，是因为大量重要的实际问题都是 NP 完全的，包括子集和。这些问题中没有一个已知有比指数时间更快的算法，尽管一些 NP 完全问题承认其解决方案的可行近似值。

关于计算复杂性，仍有很多未解之谜。我们知道，严格来说，更多的特定计算资源可以让我们解决更难的问题，例如 TIME[n] 严格包含在 TIME[n1.01] 中，SPACE 和其他度量也是如此。然而，不同计算资源之间的权衡仍然不太清楚。很明显，P 包含在 NP 中。此外，NP 包含在 PSPACE 中，因为在 PSPACE 中我们可以系统地尝试 NP 计算的每一个分支，为后续分支重用空间，如果这些分支中的任何一个导致接受，则接受。PSPACE 包含在 EXPTIME 中，因为如果 PSPACE 机器花费的时间超过指数时间，那么它恰好重复了某些配置，因此它一定处于无限循环中。以下是上述类别之间的已知关系：

P⊆NP⊆PSPACE⊆EXPTIME

然而，虽然很明显 P 严格包含在 NP 中，NP 严格包含在 PSPACE 中，PSPACE 严格包含在 EXPTIME 中，但这些不等式都没有得到证明。事实上，甚至不知道 P 与 PSPACE 不同，也不知道 NP 与 EXPTIME 不同。从上述内容中唯一已知的正确包含是 P 严格包含在 EXPTIME 中。有关不同计算资源的相对能力的其余问题是计算理论中尚未解决的基本问题。

下图列出了我们讨论过的所有复杂性类别以及其他一些类别。该图来自《描述复杂性》[Immerman，1999]中的工作，该图表明所有重要的复杂性类别都有描述性特征。Fagin 通过证明 NP = SO∃ 开启了这个领域，即，一个属性在 NP 中当且仅当它可以在二阶存在逻辑中表达 [Fagin，1974]。

Vardi 和本文作者后来独立证明了 P = FO(LFP)：一个属性在 P 中当且仅当它可以在一阶逻辑中表达，加上最小不动点算子 (LFP)，该算子形式化了通过归纳定义新关系的能力。一个引人入胜的推论是 P = NP 当且仅当 SO = FO(LFP)。也就是说，当且仅当二阶逻辑中可表达的每个属性都已可以在一阶逻辑加上归纳定义中表达时，P 等于 NP。（所讨论的语言是有限有序输入结构。有关详细信息，请参阅 [Immerman, 1999]。）



可计算性和复杂性的世界

图表的右上角显示了递归可枚举 (r.e.) 问题；这包括 r.e. 完全问题，例如停机问题 (Halt)。左侧是 co-r.e. 问题集，包括 co-r.e. 完全问题 ¯Halt ——在给定输入上永不停止的图灵机集。我们在第 2.3 节末尾提到，r.e 问题集与 co-r.e 问题集的交集等于递归问题集。原始递归问题集是递归问题的严格子集。

移至图表底部，有一个用绿色虚线标记的区域，标记为“真正可行”。请注意，这不是一个数学定义的类，而是一个直观的概念，即那些可以使用我们能负担得起的计算机在合理的时间内对所有合理大小的实例进行精确解决的问题。（有趣的是，随着计算机速度多年来的急剧提高，我们对能够处理多大实例的期望也相应提高。因此，“真正可行”的边界变化速度比计算机速度的提高所暗示的要慢。）

如前所述，P 是可行问题集的良好数学包装。P 中的问题需要 n1,000 时间来解决大小为 n 的问题，因此不可行。大自然似乎是我们的朋友，也就是说，P 中自然发生的问题倾向于相对简单的算法，“自然”问题往往是可行的。对于规模为 n 的问题，所需的步数往往小于 cnk，且乘法常数 c 较小，指数 k 非常小，即 k≤2。

在实践中，自然发生的问题的渐近复杂性往往是决定它们是否可行的关键问题。对于规模为十亿的每一个实例，现代计算机可以在一分钟内处理复杂度为 17n 的问题。另一方面，对于规模为一百的某些实例，最坏情况复杂度为 2n 的问题在我们的有生之年无法处理。

如上所述，自然问题往往对于重要的复杂性类别是完整的，即图中的类别和极少数其他类别。这种迷人的现象意味着算法和复杂性不仅仅是抽象概念；它们在实践层面上很重要。我们已经取得了显著的成功，证明了我们感兴趣的问题对于一个众所周知的复杂性类别是完整的。如果该类包含在 P 中，那么我们通常只需查找已知的有效算法即可。否则，我们必须寻找可能可行的简化或近似问题。

关于 NP 优化问题的近似性有丰富的理论（参见 [Arora & Barak, 2009]）。例如，上面提到的子集和问题是一个 NP 完全问题。很可能需要指数时间才能判断给定的子集和问题是否有精确解。但是，如果我们只想看看我们是否能够达到固定位数的精度目标，那么问题就相当简单了，即子集和很难，但很容易近似。

即使是完全停机问题也有许多重要的可行子问题。给定一个程序，通常不可能弄清楚它做什么以及它最终是否会停止。然而，程序员或学生编写的大多数程序都可以被现代编译器和模型检查器自动分析、优化甚至纠正。

NP 类在实践和哲学上都非常重要。它是一类问题 S，当且仅当有一个证明 p(w) 证明 w∈S 且 p(w) 不比 w 大太多时，任何输入 w 都在 S 中。因此，我们可以非常不正式地认为 NP 有一组可能触手可及的智力努力：如果我们找到了 w 是否∈S 的答案，我们就可以说服别人我们已经找到了答案。

布尔可满足性问题 SAT 是第一个被证明为 NP 完全的问题 [Cook, 1971]，也就是说，它是最难的 NP 问题。SAT 是 NP 完全的这一事实意味着 NP 中的所有问题都可以归结为 SAT。多年来，研究人员已经构建了非常高效的 SAT 求解器，可以快速解决许多 SAT 实例 - 即找到令人满意的分配或证明不存在 - 即使对于具有数百万个变量的实例也是如此。因此，SAT 求解器被用作通用问题求解器。另一方面，已知当前 SAT 求解器无法解决的小实例类。因此，P 与 NP 问题的一部分涉及 SAT 的实际和理论复杂性 [Nordström，2015]。

计算复杂性有一套广泛的理论。本条目简要描述了该领域，将其置于原则上和实践上可计算的问题背景下。对于有兴趣进一步了解复杂性的读者，有很多优秀的书籍，例如 [Papadimitriou，1994] 和 [Arora and Barak，2009]。还有关于计算复杂性理论的条目。