IT 论文精读 · PAPER 52

The Complexity of Theorem-Proving Procedures（NP 完全性）

Stephen Cook · University of Toronto · STOC 1971

这篇论文干了什么？

1971 年，Stephen Cook 证明了一件让计算机科学至今头疼的事：有一大类问题，「验证一个答案对不对」很容易，但「从头找出答案」却可能难到天荒地老——而且它们本质上是「同一道题」，攻破任何一个就等于攻破全部。这就是那道著名悬案 P 对 NP 的起点。

先说个怪事

有些事，别人把答案摆你面前，你一眼能核对；可要你自己找出来，却难上天。一盒散拼图，拼好了你一秒看出对不对，可从散片拼起来能耗一整天。给一大桌人排座位、满足一堆「谁不能挨着谁」的要求——给你一张排好的表你立刻能检查合不合规，但从零排出来，人一多就没头绪。Cook 注意到：这种「验证容易、求解看起来极难」的问题多得数不清，而且它们全都「连在一起」。

那个点子

Cook 干了两步。第一步，他把「验证容易」的这一大类问题圈成一个家族（后来叫 NP）。第二步——也最惊人——他证明这家族里有一道题（判断一串逻辑条件能不能同时被满足，叫「可满足性」）是「最难的那个代表」：家族里任何一道题，都能被快速改写成这道题的样子。

它是怎么做到的？

关键工具叫「改写」（专业叫归约）。如果我能把问题 A 快速翻译成问题 B——A 的答案就藏在 B 的答案里——那么「B 好解」就意味着「A 也好解」。Cook 证明了：NP 这一大家族里的每一道题，都能这样翻译成那道「可满足性」题。于是它成了一把「总钥匙」：谁要是找到一个又快又通用的办法解开它，那一整个家族——几千个看似八竿子打不着的难题——就会同时被解开。反过来，几十年没人做到，也让大家越来越相信：也许根本就没有这样的快办法。

它带来了什么？

「P 到底等不等于 NP」成了计算机科学最大的悬案，悬赏一百万美元至今没人领走。实际用处也极大：当你发现手上的难题和那把「总钥匙」是「同一家的」，基本就等于收到一封通知——别再指望找到又完美又飞快的算法了，老老实实用近似、用巧办法凑合。诚实说一句：「最难」指的是最坏情况——现实里很多这类问题的具体例子，用今天的求解器照样又快又好地解出来，「同一家」不等于「这道具体题永远解不动」。

一句话记住

Cook 证明了：在「验证容易」的一大类问题里，存在一个「最难代表」，攻破它就攻破全部；而至今没人知道这样的攻破到底存不存在——这就是 P 对 NP。

想看 P / NP 的准确定义、Cook 定理怎么证的、以及那张「把计算写成逻辑题」的图？ → 切到精读版

一句话

Cook 1971 定义了「答案能在多项式时间内被验证」的问题类（后称 NP），提出用多项式时间归约比较问题的难度，并证明了历史上第一个「NP 完全」问题——命题公式的可满足性（SAT）：NP 中任何问题都能在多项式时间内归约到它。于是 SAT 成了整个 NP 的「最难代表」，「P 是否等于 NP」从一句模糊的直觉，变成了一个精确的数学问题。

Glossary · 术语表

判定问题（decision problem）：答案只有「是 / 否」的问题，如「这张地图能用三种颜色染色而相邻不同色吗」。复杂度理论主要研究这一类。
输入规模与时间复杂度：一个算法要跑多少步，写成「输入规模 n 的函数」；n 是输入的长度（数字的位数、图的节点数……）。
多项式时间（polynomial time，P）：步数不超过 n 的某个固定次幂（n、n²、n³……）就算「高效 / 可行」；对照的是指数时间（约 2ⁿ），n 稍大就成天文数字。P 就是「存在多项式时间算法的判定问题」这一类。
图灵机（Turing machine）：一台抽象的「最朴素计算机」——一条纸带、一个读写头、一张规则表，是「什么叫算法 / 可计算」的数学定义（见本站《图灵机》一篇）；复杂度就按它跑多少步来数。
确定性 vs 非确定性（deterministic / nondeterministic）：确定性机器每一步动作唯一；非确定性机器允许「同时分叉去试所有可能」，只要有一条分支走到「接受」就算成功——它是理论工具，不是真机器。
命题公式 / 可满足性（SAT）：由变量和「与、或、非」搭起来的逻辑式子；SAT 问：能不能给这些变量各赋 true/false，让整个式子为真。
归约（reduction）：把问题 A「翻译」成问题 B 的办法，使 A 的答案能从 B 的答案读出来；若翻译本身很快，则「B 好解 ⇒ A 好解」。

坐标

作者 Stephen Cook，1971 年发表于第三届 ACM 计算理论年会（STOC）。它站在图灵（1936，可计算性）与 1960 年代复杂度理论（Hartmanis–Stearns 等把「要花多少资源」本身作为研究对象）的肩上，第一次给「难解」一个精确、可操作的刻画；一年后 Karp（1972）用它证明 21 个经典问题皆 NP 完全，把这套理论推向整个算法界。苏联的 Levin 几乎同时独立得到等价结果，故又称 Cook–Levin 定理。Cook 因此获 1982 年图灵奖。

问题与动机

到 1960 年代，人们已能区分「有算法」和「没算法」（可计算性，图灵划下的那条线）。但「有算法」之内还藏着天壤之别：判断一个数是不是质数、给图找最短路，都有快算法；可另一些问题——「这张地图能不能三色染色」「一批货能不能刚好塞进若干箱子」——已知的唯一通用办法几乎都是把所有可能挨个试一遍，可能性随规模指数爆炸。人们模糊地感到这些问题「本质上更难」，却说不清「难」到底是什么，更无法证明它们真的没有快算法。缺的是一把统一的尺子：怎样精确地说「问题 A 至少和问题 B 一样难」？Cook 这篇，就是把这把尺子造了出来。

核心思想 / 方法

两个类：P 与 NP

P：存在确定性多项式时间算法的判定问题——「能高效求解」。NP：对一个「是」的实例，若存在一份长度不超过多项式的「证据 / 答案」，能在多项式时间内被验证为真，则该问题属于 NP——「答案能高效验证」。等价地，NP 是非确定性图灵机多项式时间可判定的问题（机器先「猜」出证据、再验证）。例：SAT 属于 NP——给一组变量赋值当证据，代进公式一算就知真假。显然 P ⊆ NP（能解就能验证）。核心悬念是反过来：P = NP 吗？能高效验证的，是否都能高效求解？

图 1 · 假设 P≠NP 时的版图：P（能求解）在 NP（能验证）之内，NP 完全问题位于 NP「最难的边缘」；若 P=NP，三块塌成一块。

归约：一把比较难度的尺子

Cook 定义多项式时间归约：若能用一个多项式时间的过程，把 A 的每个实例转成 B 的一个实例、并保持答案（A 为「是」当且仅当转出的 B 为「是」），就记 A ≤ B，直觉是「A 不比 B 难」——因为一旦有了解 B 的快办法，就能先翻译再解 B，顺带快速解掉 A。归约可传递、可组合。有了这把尺，「谁最难」才第一次有了确切含义。

图 2 · 归约：把 A 快速翻译成 B 且答案不变，于是「B 好解」自动带来「A 好解」——这就是比较难度的标尺。

NP 完全与 Cook 定理

若 NP 中每一个问题都能归约到 L，且 L 自己也在 NP 里，就称 L 为 NP 完全——它是 NP 里「最难的代表」：只要解开任何一个 NP 完全问题（把它放进 P），整个 NP 就随之塌进 P，P = NP 立刻成立。Cook 的定理是：SAT 是 NP 完全的。（Cook 原文用命题公式的「重言式 / 恒真式」判定来表述，它与 SAT 互为补问题、等价可换。）这句话背后是一个惊人的事实——一道具体的逻辑判定题，浓缩了整个 NP 的全部难度。

证明直觉：把「计算」写成一道逻辑题

怎么证明 NP 里五花八门的问题都能变成 SAT？Cook 的招不是逐个问题去凑，而是针对「验证它的那台机器」。任何 NP 问题背后，都有一台非确定性图灵机 M 在多项式步数内判定它。把 M 在输入 x 上的整个运行过程摊成一张表格（tableau）：行是时间步、列是纸带格子，每格记那一刻的符号，外加读写头位置与机器状态。

然后用布尔变量描述表格里每一格的内容，再用一组子句把「游戏规则」钉死：① 第一行必须正好是输入 x；② 相邻两行必须符合 M 的转移规则（每一步都合法）；③ 某一行出现「接受」状态。这样拼出的公式 φ，可满足 ⟺ M 存在一条走到接受的运行。而表格只有多项式那么大，φ 也只有多项式那么大、还能在多项式时间内造出来。于是「M 接受 x 吗」被翻译成了「φ 可满足吗」——任意 NP 问题 ≤ SAT，定理得证。关键洞察是：可满足性足够「万能」，能编码「计算的每一步是否合法」这件事本身。

图 3 · Cook 定理证明骨架：把非确定图灵机的运行摊成表格，用布尔子句钉死「起始正确、每步合法、终于接受」，公式可满足当且仅当机器接受——于是一切 NP 问题都归约到 SAT。

关键结果

这是一篇理论论文，没有 benchmark 数字，但它给出的是可检验的硬结论：

第一个 NP 完全问题：SAT（及重言式判定）对 NP 完全——NP 中每个问题都多项式归约到它。
Cook 还指出另一个组合问题（子图相关）的完全性，示范这把工具能复用、不是一次性技巧。
真正的「引爆」来自 Karp 1972：用同样的归约手法，证明 21 个来自逻辑、图论、调度、集合的经典问题（可满足性、团、顶点覆盖、哈密顿回路、划分、背包类……）统统 NP 完全——它们表面天差地别，实为「同一道题」的不同外衣。至今已知的 NP 完全问题数以千计。

为什么重要 / 影响

它给「难解」下了精确、可操作的定义，奠定了计算复杂度理论的中心结构：P、NP、归约、完全性。由此：

算法设计的路标：证明你的问题 NP 完全，等于（在普遍相信的 P≠NP 前提下）宣告「别再找又快又精确的通用算法」——转而求近似算法、启发式、参数化或专用求解器。这省下了无数徒劳的攻坚。
催生 SAT 求解器工业：既然万物可归约到 SAT，把实际问题（硬件验证、规划调度、程序分析）编码成 SAT、再交给高度优化的求解器，成了一件通用武器。
P vs NP 成头号开放问题：2000 年入选克雷数学所七个「千禧年难题」之一，百万美元悬赏至今空置。Cook 本人获 1982 年图灵奖。

局限与批评

没有解决 P vs NP：定理告诉你这些问题「同生共死」，却没说它们到底难不难；至今悬而未决，学界普遍相信 P≠NP 但拿不出证明。
只刻画最坏情况：NP 完全是就最坏实例而言的；现实里大量 NP 完全问题的典型实例被现代求解器又快又好地解决（百万变量的 SAT 例子并不稀奇）——「NP 完全」≠「实践中不可解」。
渐进 ≠ 实用：多项式时间被当作「高效」的代名词，但 n¹⁰⁰ 也是多项式；反过来某些指数算法在小规模上很好用。这是理论上方便的约定，不总对应现实效率。
归约口径之别：Cook 用的是较宽的多项式时间图灵归约；Karp 之后，学界多改用较严格的多对一归约，两种「完全性」定义在细节上不同。
独立发现与署名：Levin 在苏联几乎同时（甚至更早）得到「通用搜索问题」的等价结果，长期被西方忽视，故正名为 Cook–Levin 定理。

要点

① 一句话：Cook 定义 NP、用多项式归约比较难度，并证明 SAT 是第一个 NP 完全问题。

② 痛点：可计算之内仍有天壤——有些问题只会「穷举试遍」，却无法精确说清「更难」到底是什么。

③ 两个类：P＝能高效求解；NP＝答案能高效验证（等价于非确定多项式时间）；显然 P⊆NP，问 P=NP？

④ 尺子：多项式时间归约 A ≤ B——「B 好解则 A 好解」，让「最难」第一次有定义。

⑤ 完全性：NP 完全＝NP 中最难代表；解开任一个，整个 NP 就塌进 P。

⑥ Cook 定理：SAT 是 NP 完全；证明靠把「某台非确定机是否接受」编码成一个可满足性公式（运行表格 → 布尔子句）。

⑦ 影响：Karp 随即找出 21 个、如今数以千计；成算法设计路标、催生 SAT 求解器；P vs NP 列千禧难题，Cook 获图灵奖。

⑧ 局限：P vs NP 仍未解；NP 完全是最坏情况、不等于实际难解；多项式≠总实用；Levin 独立发现（Cook–Levin）。