第19章：复杂度作为推理的几何——为什么有些推理根本不能被加速

P≠NP 不是关于机器速度的命题。它是关于问题内在结构的命题。

第18章结尾留下了一个不舒服的观察：即使有了完整的因果图，在图上做推断——识别因果效应、计算可识别的表达式——在复杂情况下代价急剧上升。这不是算法写得不够好，而是问题本身就难。

这个"本身就难"，需要一个精确的数学含义。

在形式系统的语境里，"难"有一个量化的版本：从公理到定理需要多少步？第14章提到，验证一个证明是多项式时间可完成的，但发现一个证明没有通用的高效算法。这个不对称性，在计算理论里有一个正式的名字，叫做 P 和 NP 的分离——如果它成立的话。

本章要做的事情，就是把这个"难"的直觉，变成一个精确的几何图景。

19.1 问题的内在结构

先从一个让人意外的区分开始。

有两种"困难"，表面相似，本质不同。

第一种困难：问题很大，数据很多，计算机需要跑很久。这是工程意义上的困难，可以通过更快的硬件、更聪明的算法、更多的并行计算来缓解。这种困难没有原则性边界。

第二种困难：无论你用什么算法，无论硬件多快，某些问题就是需要指数级的时间。这是数学意义上的困难，不是工程问题，而是问题本身的内在结构决定的。

复杂度理论关心的是第二种困难。它的问题不是"这个算法快不快"，而是"这个问题能不能被任何算法快速解决"。

兔狲教授评

很多人听到 P≠NP 就联想到"计算机不够快"。这是完全错误的理解。P≠NP 说的是：即使给你无限快的计算机，某些问题依然需要指数时间。速度买不来结构。问题的几何形状，不因机器变快而改变。

为了让"快速"有精确含义，需要一个衡量尺度。

时间复杂度：对于一个问题，输入规模为 $n$ ，最优算法需要多少步才能给出答案？如果存在算法使得步数是 $n$ 的多项式（ $n^{2}, n^{3}, n^{100}$ ……），称这个问题是多项式时间可解的；如果所有已知算法都需要指数级步数（ $2^{n}, n!, \dots$ ），这个问题在实践中随着 $n$ 的增长迅速变得不可解。

多项式和指数之间的鸿沟，是复杂度理论的核心分界线。 $n = 100$ 时， $n^{10} = 10^{20}$ ，已经很大； $2^{100} \approx 10^{30}$ ，比宇宙中的原子数还多。随着 $n$ 再增大，这个差距只会变得更加荒诞。

19.2 P 与 NP：两种能力

现在可以定义两个最重要的复杂度类。

P（多项式时间）：所有可以在多项式时间内求解的判定问题的集合。判定问题是回答"是或否"的问题：这个图里有没有哈密顿回路？这个数是不是质数？这个命题在这个逻辑系统里可证吗？

"在 P 里"意味着：存在一个算法，对任何规模为 $n$ 的输入，在 $O (n^{k})$ 步内给出正确的"是"或"否"（ $k$ 是某个固定常数，不依赖输入）。

NP（非确定性多项式时间）：所有可以在多项式时间内验证答案的判定问题的集合。更精确地：对于"是"的实例，存在一个多项式长度的证书，可以在多项式时间内被验证。

"在 NP 里"意味着：如果答案是"是"，那么有人能向你展示一个简短的证明，让你在多项式时间内确认这个证明是正确的。

注意这里的不对称性——这正是第14章那个不对称性的回声：验证一个证明是高效的（多项式时间），发现一个证明不一定是高效的（可能需要指数时间）。

P 里的所有问题都在 NP 里（如果你能在多项式时间内解决一个问题，你当然也能在多项式时间内验证答案——直接再算一遍就是了）。问题是：NP 里的问题都在 P 里吗？

这就是 $P \overset{?}{=} NP$ 的问题。

为什么几乎所有人相信 P ≠ NP

严格地说，P ≠ NP 是一个未被证明的猜想。但数十年来，数学家和计算机科学家的经验积累出了一个强烈的信念：求解和验证之间，存在一道根本的鸿沟。如果 P = NP，那么任何可以被快速验证的解，都能被快速找到——这将意味着密码学的崩溃（破解加密和验证密钥一样快），意味着创造力等价于检验，意味着数学证明的发现和验证之间没有本质区别。这个图景对我们关于推理和创造的所有直觉都是毁灭性的。P ≠ NP 的信念，是对"求解比验证更难"这个基本直觉的数学表达。

19.3 NP 完全：最难的问题

NP 里的问题不是一视同仁的。有些问题，如果能快速解决，就能快速解决 NP 里的所有问题。这些问题叫做 NP 完全（NP-complete）。

这个概念需要一个工具：多项式时间归约。如果问题 $A$ 可以多项式时间归约到问题 $B$ （记作 $A \leq_{p} B$ ），意思是：存在一个多项式时间的变换，把任意 $A$ 的实例转化为等价的 $B$ 的实例。如果你能快速解决 $B$ ，那么通过这个变换，你也能快速解决 $A$ 。

NP 完全的定义：问题 $C$ 是 NP 完全的，当且仅当：

$C \in NP$ （答案可以被快速验证）；
对所有 $A \in NP$ ，有 $A \leq_{p} C$ （NP 里所有问题都可以归约到 $C$ ）。

第一个被证明是 NP 完全的问题，是 SAT（布尔可满足性问题）：给定一个布尔公式，是否存在一组变量赋值使公式为真？Stephen Cook 1971 年的证明——Cook-Levin 定理——是复杂度理论的奠基之作。

SAT 是 NP 完全的，意味着：如果你能快速判断布尔公式是否可满足，你就能快速解决 NP 里的所有问题，包括旅行商问题、图着色问题、背包问题……以及，某些因果发现问题。

SAT 为什么是推理的核心

布尔可满足性问题，在形式逻辑的语境里，就是：给定一组命题公式，是否存在一个真值赋值使它们都为真？这正是寻找模型的问题——逻辑语义的核心操作。第14章说"验证一个证明是多项式时间可完成的"，对应的是：给定一个候选赋值，检验它是否满足公式，只需逐项代入，多项式时间完成。而"发现"一个使公式为真的赋值，就是 SAT——NP 完全。推理的不对称性，在这里获得了精确的计算刻画。

19.4 停机问题：比 NP 更深的边界

P 和 NP 的讨论，预设了问题至少是可以被算法回答的——只是快慢不同。但存在另一类边界：某些问题根本不存在任何算法来回答它们，无论给多少时间。

停机问题：给定一个程序和它的输入，这个程序最终会停止，还是永远运行下去？

图灵 1936 年证明了：不存在任何算法，可以正确回答所有程序的停机问题。

证明是经典的自指构造，和哥德尔的方法在本质上相同。

假设存在一个程序 $H (P, I)$ ，它接受程序 $P$ 和输入 $I$ ，总是在有限步内正确回答： $P$ 在输入 $I$ 上会不会停机。现在构造另一个程序 $D$ ：

D (P) = {\begin{cases} 永远循环 & 若 H (P, P) = 停机 \\ 停机 & 若 H (P, P) = 不停机 \end{cases}

$D$ 把程序 $P$ 当成自己的输入，问 $H$ ：" $P$ 在输入 $P$ 上会不会停机？"然后做相反的事。

现在问： $D$ 在输入 $D$ 上会不会停机？

若 $H(D, D) = $ 停机： $D$ 会永远循环—— $H$ 撒谎了。
若 $H(D, D) = $ 不停机： $D$ 会停机—— $H$ 又撒谎了。

$H$ 在任何情况下都给出了错误答案。矛盾。所以 $H$ 不存在。

这个证明的结构，和第15章哥德尔句 $G$ 的构造完全平行： $G$ 说"我在这个系统里不可证"， $D$ 说"我和 $H$ 的判断相反"。两者都通过自指，将任何试图完全刻画自身的系统逼入矛盾。停机问题和不完备定理，是同一枚硬币的两面。

兔狲教授评

一旦你看清这一点，哥德尔和图灵的两个"震撼结果"就变成了一个结果，用了两种语言表达。数学的自指和计算的自指，结构完全相同。如果你只是分别记住了两个定理，你其实还没理解它们。

从逻辑到计算的等价

更精确地说：皮亚诺算术里的哥德尔不完备性，可以通过图灵机的停机问题来证明，反之亦然。递归函数论（Computability Theory）建立了这个精确对应：一个命题在系统里不可判定，当且仅当对应的计算问题不可判定。不完备性不是逻辑特有的现象，而是任何足够强的形式系统——包括通用计算机——所共有的内在限制。

停机问题不可判定，意味着存在一道比 NP 完全更深的边界：不是"需要指数时间"，而是"没有任何有限时间内的算法"。复杂度的图景，从下往上大致是：

P \subseteq NP \subseteq PSPACE \subseteq \dots \subseteq 可判定 \subseteq 可枚举 ⊊ 全部问题

停机问题生活在"可枚举但不可判定"的层级——你可以在有限步内验证一个停机的程序确实停机了（直接运行，等它停），但无法在有限步内确认一个不停机的程序永远不会停（你等了一亿步，它还没停，这不代表它永远不会停）。

19.5 Oracle 分离：边界是真实的

有一个自然的问题：P 和 NP 之间的分离，是否只是我们目前技术的局限，而非原则性的边界？

**相对化（Relativization）**给了我们部分答案。

给一个算法配备一个 Oracle——一个黑盒，可以在一步内回答某类特定问题。对 Oracle 的选择不同，P 和 NP 之间的关系可以发生变化。Baker、Gill 和 Solovay 1975 年证明：

存在 Oracle $A$ ，使得相对于 $A$ ， $P^{A} = {NP}^{A}$ ；
存在 Oracle $B$ ，使得相对于 $B$ ， $P^{B} \neq {NP}^{B}$ 。

这个结果的含义是：P ≠ NP 的证明，不能用相对化技术完成。任何基于计数或代数的证明路线，如果它"相对化"（即对 Oracle 模型仍然成立），就无法区分 P = NP 和 P ≠ NP 两种世界。

这不是说 P ≠ NP 无法证明，而是说证明必须是非相对化的——必须深入到计算的本质结构里，而不是停留在算法层面的操作。这个要求，至今没有人满足。

已知的技术屏障——相对化、自然证明、代数化——每一个都说明：通往 P ≠ NP 的道路，不经过我们熟悉的任何路线。这个问题的深度，也许和它的重要性相称。

19.6 推理的代价：回到因果

第18章的因果发现问题，现在可以在复杂度的框架里精确定位了。

因果结构学习：给定变量集上的观测数据，找到与数据一致的因果图。在一般情况下——变量数为 $n$ ，可能的 DAG 数量超指数地随 $n$ 增长，穷举搜索根本不可行。

已知结果：

在某些限制下（假设因果马尔科夫条件和忠实性条件），PC 算法可以在多项式时间内恢复因果图的骨架（无向边）；
但确定边的方向——区分马尔科夫等价类内的不同图——在一般情况下是 NP 难的；
在存在隐变量的情况下，即使骨架也难以恢复。

这个结果说明：精确的因果推断，在计算上是根本困难的。不是因为算法没写好，而是因为问题本身属于 NP 难的范畴。哪怕有完美的数据，也无法系统性地快速找到答案。

这是对第18章的一次回击：给我图，我能做因果推断——但拿到图本身，代价可能无法承受。

因果推理的困境，是推理普遍困境的一个实例：精确推理往往是计算上不可行的。这不是算法的问题，这是问题空间的几何形状决定的，没有捷径。

19.7 证明与计算的等价

第14章说过：证明是句法对象，验证是多项式时间可完成的，发现不一定。第19章把这个直觉变成了严格的语句。

命题逻辑的可满足性（SAT）是 NP 完全的：发现一个使给定公式为真的赋值，和发现一个证明，在计算复杂度上是等价的。

更深的对应：证明长度和计算步数。一个命题在某个系统里的最短证明的长度，对应着在某个计算模型里解决对应问题所需的最少步数。证明复杂度（Proof Complexity）正是研究这个对应关系的领域——它把逻辑系统的表达能力和计算复杂度类联系起来。

一个已知的结论：如果存在某个命题逻辑证明系统，能对 SAT 的任何不可满足实例给出多项式长度的不可满足证明，那么 NP = coNP。换言之，任何足够弱的证明系统，都必然存在需要指数长度证明的真命题。这不是哥德尔不完备性——不是说命题不可证，而是说即使可证，证明也可能长得无法使用。

这是第14章留下的那个悬念（"证明的长度有意义吗"）的正式回答：有，非常有意义。证明长度是复杂度的镜像，形式系统的表达效率直接关系到计算问题的难度。

悬而未决

P ≠ NP 是真的吗？ 绝大多数人相信是的，但没有人证明。这是数学里最重要的未解问题之一。如果它是假的——如果 P = NP——那么所有可以被快速验证的问题都可以被快速解决，密码学崩溃，创造力等价于检验，推理的内在代价消失。这个世界和我们所有的直觉相悖，但逻辑上不自相矛盾。我们对 P ≠ NP 的信念，比对它的证明更坚定。

复杂度类的边界是尖锐的吗？ P 和 NP 之间是否存在中间地带——既不在 P 里，又不是 NP 完全的问题？Ladner 定理告诉我们：如果 P ≠ NP，那么这样的问题存在，叫做 NP 中间问题（NP-intermediate）。图同构问题被怀疑是这样的问题，但目前无法证明。复杂度的图景，比 P 和 NP 两个类丰富得多。

精确推理不可行，近似推理怎么办？ P ≠ NP 说的是精确解很难找。但也许找一个"足够好"的近似解，代价要小得多？对于某些问题，这是对的——存在多项式时间的近似算法，能保证解的质量在最优解的某个比例之内。但对另一些问题，近似同样是 NP 难的——即使允许误差，也逃不掉指数代价。这个区分是第20章的主题：启发式不是随意的近似，它是一种有精确数学合同的承诺。

思考题

★ 热身

对以下问题分类：它在 P 里、在 NP 里（但不知道是否在 P 里）、还是不可判定的？只需要给出分类和一句话理由。

给定一个有序整数数组和一个目标值，判断目标值是否在数组里（二分搜索）
给定一个布尔公式，判断它是否可满足（SAT）
给定一个程序，判断它是否永远不输出任何内容
给定一个图，判断它是否存在哈密顿回路
给定两个程序，判断它们对所有输入是否产生相同的输出

★★ 推导

归约的方向：如果 $A \leq_{p} B$ （ $A$ 可以多项式时间归约到 $B$ ），且 $B \in P$ ，那么 $A \in P$ 。反过来，如果 $A \leq_{p} B$ 且 $A$ 是 NP 完全的，这对 $B$ 意味着什么？分两种情况： $B \in NP$ 和 $B \notin NP$ 。
停机问题的变体：以下三个停机问题的变体，哪个可判定，哪个不可判定？说清楚理由。
- 给定程序 $P$ 和输入 $I$ ， $P$ 在 $I$ 上是否在 $10^{100}$ 步内停机？
- 给定程序 $P$ ， $P$ 是否对所有输入都停机？
- 给定程序 $P$ ， $P$ 是否对某个输入停机？

★★★ 挑战

第14章说：验证一个命题逻辑证明是多项式时间可完成的。这意味着"命题逻辑定理证明"——给定一个命题 $φ$ 和一个候选证明序列，判断这个序列是否是 $φ$ 的合法证明——在 P 里。

现在考虑一个不同的问题："给定命题 $φ$ ，判断 $φ$ 是否是定理（即是否存在证明）"。

这个问题在 NP 里吗？（提示：什么充当"证书"？）
SAT 是 NP 完全的，而 SAT 等价于"给定命题公式，判断它是否可满足"。"可满足"和"是定理"在命题逻辑里是什么关系？
把这两件事联系起来：如果 P = NP，对数学中"发现证明"这件事意味着什么？如果 P ≠ NP，是否意味着某些数学定理的证明，即使存在，也原则上找不到？

第3个问题触及一个真实的数学哲学问题，目前没有共识答案。试着区分"证明存在但找不到"和"证明不存在"这两种情况——用本章的语言把这个区分写清楚。

第19章：复杂度作为推理的几何——为什么有些推理根本不能被加速 ​

19.1 问题的内在结构 ​

19.2 P 与 NP：两种能力 ​

19.3 NP 完全：最难的问题 ​

19.4 停机问题：比 NP 更深的边界 ​

19.5 Oracle 分离：边界是真实的 ​

19.6 推理的代价：回到因果 ​

19.7 证明与计算的等价 ​

悬而未决 ​

思考题 ​