斯蒂芬·库克

破除误解：NP 完全不是「解不了」#

把 NP 完全读成「不可计算」或「永远没有算法」，是最常见的错位。SAT 有算法：枚举 $2^n$ 种赋值即可。库克证明的不是无算法，而是：若不存在多项式时间算法，则这一整类「好验证」的问题都没有。可判定与高效可判定是两层问题；前者早已被图灵机模型说清，后者才是 1971 年真正打开的战场。

第二个误解是把「库克提出了 P 对 NP」当成个人发明。多项式时间作为「可行」的候选，1960 年代已在科巴姆（Alan Cobham）、埃德蒙兹（Jack Edmonds）等人的文字里出现；库克的贡献是给出完全性：不是再列一份难例清单，而是证明存在一个问题，所有 NP 问题都多项式归约到它。

第三个误解来自工程现场。今日的 SAT 求解器 能解开百万变量的工业实例，于是有人宣布「P = NP 在实践中已成立」。最坏情况硬度与平均情况可解可以同时为真。求解器利用结构、启发式与随机重启；库克的完全性说的是：存在一族实例，任何多项式算法都会在其上失败——若 P ≠ NP。工业上的「经常很快」并不否证最坏情况的地图。

现场：一张计算表如何变成公式#

要看懂库克 1971 年的构造，不必先背复杂度类的口号。从一台非确定性图灵机说起。

所谓 NP，可以定义为：存在一台非确定性图灵机 $M$，在输入 $x$ 上于多项式步 $T = n^{O(1)}$ 内接受，当且仅当 $x$ 属于语言。非确定性的含义是：每一步可以有若干合法转移，接受意味着存在一条转移序列走到接受态。验证者版本与此等价：存在一份短证据 $w$，确定性算法在多项式时间内核对 $(x,w)$。

库克把「存在一条接受计算」写成布尔公式。想象一张表，行是时间 $0,1,\ldots,T$，列是磁带格。格 $(i,j)$ 记录第 $i$ 步时第 $j$ 个格子上的符号；磁头所在格还要记下状态。这张表合法，当且仅当：

• 第 0 行是 $x$ 的起始格局；
• 相邻两行只在磁头附近一个常数大小的窗口内变化，且变化符合 $M$ 的转移函数；
• 某格出现接受态。

每个局部条件只涉及常数个变量，因而可写成常数大小的子句。整张表的合法性是这些子句的合取。公式可满足，当且仅当存在一条接受计算。把任意 NP 机器的运行这样编码，就得到：任意 NP 语言多项式归约到 SAT。

这就是后来所称的库克–列文定理。它不提供 SAT 的快速算法，它提供一张等价证书：SAT 若属 P，则 NP 中每一个语言都属 P。编码的多项式开销来自表的尺寸 $O(T^2)$ 以及每个窗口的常数子句；归约本身是确定性、多项式时间的。

库克选 SAT，不是因为他预见到芯片验证会靠求解器吃饭。他选的是一种能把「局部一致性」写干净的语言：磁带窗口只涉及常数个符号，布尔连接词恰好表达这些约束。问题选择先于名录。后来工业 SAT 的成功，是这份书写格式的历史讽刺，不是 1971 年论文的目标函数。人物页若把库克写成「P 对 NP 的发明人」，会把完全性定理压成一句口号；他真正钉住的是：哪一种日常语言配得上做整个类的代表。

原文用的归约比今天教科书更宽。库克允许算法在归约过程中多次询问目标问题（图灵归约，又称库克归约）。卡普 1972 年改用多一归约：把实例一次映射成另一个实例，答案相同。他从 SAT 出发证明了二十个组合问题完全，连同 SAT 共二十一个，史称「卡普的 21 个 NP 完全问题」，对象见 Karp 1972。多一归约更严，也成为 NP 完全性的标准定义。库克证明了存在性，卡普证明了组合问题的海洋与 SAT 同生共死。

列文的平行发现，以及完全性真正改变了什么#

苏联数学家列昂尼德·列文（Leonid Levin）几乎同时独立给出等价图景。他的 1973 年俄文论文谈的是「通用搜索问题」：存在一些问题，任何搜索任务都可以有效地译成它们。西方文献过了数年才充分对照。今日写「库克–列文」，不是客套，是承认同一数学对象在冷战隔绝下被发现了两次。

完全性改变的是提问方式。在此之前，人们可以说「旅行商看起来很难」「定理证明看起来很难」，却无法证明它们一样难。有了多项式归约，难度可以传递：若 A 归约到 B 且 A 已完全，则 B 至少一样硬。卡普随后把三维匹配、顶点覆盖、哈密顿回路、图着色、背包判定版等送进同一等价类。一张图论或调度上的新问题，证明 NP 完全的标准动作从此变成：给出到 SAT 或到某个已知完全问题的归约，而不是重新编码整台图灵机。

库克本人后来说，他当时并没有把「P 对 NP」写成千禧年问题的句式。那句话是社区在 1970 年代逐渐钉下来的。克莱数学研究所 2000 年把它列为七个千禧年问题之一，悬赏一百万美元。奖金说明的是难度，不是进度。到 2026 年，既没有被社区接受的相等证明，也没有被社区接受的分离证明。相对化、自然证明与代数化表明，一批看似通用的技术根本碰不到它，见 P vs NP 的证明障碍。

证明复杂性：把「短证明」本身当成资源#

库克没有停在完全性。1979 年，他与雷克豪（Robert Reckhow）把命题证明系统写成对象：一个证明系统是多项式时间可检验的，若证明长度对重言式而言有多项式上界，则 NP = coNP。换言之，若每个真命题都有短的命题演算证明，则「不存在短证据」这类 coNP 命题也会落入 NP。P 对 NP 之外，还有一条平行的裂隙：证明会不会比定理本身短得多。

这条线后来叫做证明复杂性。库克关心的具体系统包括有界算术（PV 等，用于刻画多项式时间可证的数论）以及弗雷格系统、消解系统。1985 年哈肯（Armand Haken）证明鸽巢原理在消解下需要超多项式长度，是早期的超级多项式下界。库克的纲领是：要分离复杂度类，也许得先看清「证明」作为计算资源有多贵。这与 艾伦·图灵 把可判定性写成机器资源、唐纳德·克努特 把运行时间写成渐近分析，是同一精神在不同层上的延伸——对象从「停不停」「跑多久」换成「证明显得多长」。

有界算术把「哪些定理能在弱系统里证明」与「哪些函数可在多项式时间计算」对齐。库克与他人发展的 PV、$S^1_2$ 等系统，让复杂性类第一次有了对应的形式理论：可证性本身被分层。这不是科普里的「哥德尔说有不可证命题」，而是更细的问题——即便命题在皮亚诺算术里可证，它是否有短的、低复杂度的证明。NP 完全性给出搜索的下界候选；证明复杂性给出验证与证明长度的下界候选。两条线在库克职业生涯里始终并行。

电路下界是平行的第三条线。若 NP 完全问题需要超多项式大小的布尔电路，则 P ≠ NP。已知下界却卡在很弱的模型：常数深度、单调电路、受限门类型。自然证明障碍表明，一类「建设性」的组合性质若也能把伪随机函数与真随机函数分开，就不能用来证明 NP 的超多项式电路下界——除非伪随机发生器不存在。库克的完全性给出要分离的对象；障碍结果表明，分离所用的证明技术本身会撞墙。把 1971 年的定理读成「问题已精确提出，只差一个聪明的下午」，忽略了这堵后来才看清的墙。多伦多组持续投入证明复杂性，部分正是因为电路路线被堵住之后，命题证明长度仍可能泄漏复杂度类的裂隙。

窗口编码还有一处教科书常省略的精度。磁带上绝大多数格子在一步之内不变，真正需要子句约束的是磁头附近三个格子的转移。库克把不变区域写成复制约束，把转移写成有限查表。变量数目随 $T^2$ 增长，但每个变量只出现在常数个窗口里，公式是稀疏的。稀疏性后来成为 SAT 求解器能吃下工业实例的结构来源之一：不是因为 NP 完全被取消，而是因为归约产生的公式带有局部性，局部性可被单元传播与子句学习抓住。完全性与可解性在同一份公式上叠着两层故事。

1982 年图灵奖#

库克获 1982 年 ACM 图灵奖，表彰他「以深刻而重要的方式推进了我们对计算复杂性的理解」。卡普于 1985 年获奖。列文没有分享这两次奖项，这成为复杂性史教学里必须补上的一笔：制度与语言边界会改写优先权的公众版本，即使数学对象相同。

库克长期任教于多伦多大学，同时保持美国与加拿大学术身份。他的学生与多伦多理论组把证明复杂性、电路复杂性和复杂性类分离做成了可持续的研究方向，而不是一篇 1971 年论文的纪念馆。奖项钉住的是完全性这一击；实验室里真正延续的，是把「难」写成可比较、可归约、可设置下界的语言。

代价与争议#

归约口径。 库克归约允许自适应询问，卡普归约不允许。多数 NP 完全性结果在两种口径下同时成立，但并非所有。教学上若把 1971 年原文直接读成今天教材里的多一归约，会抹掉定义收紧的十年。评价库克时，应同时看到：他给出了完全性问题的存在，而标准定义是社区随后选定的更窄工具。

优先权与命名。 「库克定理」「库克–列文」「卡普–库克」在不同教科书里轮换。更准确的说法是：库克证明 SAT 对 NP 完全（在他的归约下），列文独立给出通用搜索问题，卡普展示完全性在组合问题上的广度。三人做的不是同一篇论文的三个署名，而是同一概念的三次定型。

与求解器文化的紧张。 库克的硬度是最坏情况、渐近、以多项式为「高效」门槛的。工业 SAT、SMT 与约束求解走的是另一套判据：典型实例、超时限制、工程启发式。两者互相指责对方「不食人间烟火」或「没有理论」时，真正的裂隙其实很清楚——它们优化的目标函数不同。复杂性理论需要最坏情况，才能把密码学的单向函数、近似算法的不可近似性放在同一张地图上；求解器需要结构，才能在芯片验证和调度里活下来。库克的定理没有被求解器推翻，求解器也没有因为定理而变得不正当。

P 对 NP 的公众叙事。 把整个理论计算机科学说成「就等这一个问题」，会低估库克自己后来的证明复杂性工作，也会低估电路下界、交互式证明、去随机化等已经改写过地图的进展。P 对 NP 是旗帜，不是唯一的领土。库克本人的论文目录对此更为诚实：完全性是起点，不是墓志铭。

库克选择 SAT 的证明风格，是编译而不是机智构造。他承认非确定机是 NP 的定义装置，再问哪一种日常语言能够一字不差地写下这台机器的每一步。布尔公式胜出，因为它的连接词恰好表达局部约束。完全性于是变成一种写作习惯：先固定一个已知完全的问题，再问新问题能否把它吸收进去。这种习惯改变了问题选择的伦理。在 1971 年以前，一个组合问题「难」，常常是经验判断。完全性把「难」改写成可检验的关系：它与 SAT 同生共死。你仍然不知道 SAT 本身是否有多项式算法，但你知道自己没有在一个孤立的孤岛上工作。

1982 年图灵奖演讲稿把 NP 完全、多项式层级与尚未解决的分离问题放进同一张公共叙述。他没有把 1971 年的定理说成终局。四十年后这道题仍然开放。图灵意义上的可判定性边界早已划清，难的是资源。库克站在那条已经划清的边界内侧，追问多项式这个具体资源。完全性给出的是地图，不是判决。

跨域连接#

• 证明：库克–列文把「存在一条接受计算」编译成可满足公式，等于把机器运行写成命题证明的对象。库克–雷克豪更进一步：若所有重言式都有多项式长证明，则 NP 与 coNP 重合。难的不只是找解，还有短证明是否存在。把证明长度当资源，复杂性才从算法表扩展成逻辑表。
• 组合学：卡普的归约链把 SAT 送进匹配、覆盖、划分、背包。完全性因此不是逻辑学内部的珍玩，而是组合搜索的通用货币。一个新的组合问题要定位自己，标准动作是给出归约，而不是凭感觉说「看起来像旅行商」。
• 图论：哈密顿回路、顶点覆盖、三色，是完全性进入图论的前门。图上的局部约束（边、色、圈）特别适合写成子句窗口，这也解释了为何库克的表方法能被卡普迅速换成图论语言：磁带窗口与图的局部性是同一类有限检查。
• 玻尔兹曼统计力学：随机 SAT 的可满足与不可满足之间存在相变，求解器的运行时间在相变附近鼓起。统计物理把「典型实例」写成吉布斯测度与阈值；库克的完全性管的是最坏情况。两套语言必须分开：相变解释为何有的随机公式好解，并不给 P 对 NP 提供证明，也不否定完全性。
• 信息哲学：完全性改写的是「知道一个问题很难」这句话的含义。在库克之前，难是印象；在他之后，难可以是归约闭包里的位置。知识在这里不是一条孤立命题的真值，而是它在等价类中的坐标——你若知道 SAT 的算法命运，就知道一整族问题的命运。

人物小记：把难度写成可以传递的关系#

库克不是公众人物。他的影响几乎全部通过定义与归约进入教科书，而不是通过公司或开源项目。这种安静有其代价：P 对 NP 的文化名声远远盖过证明复杂性，也盖过他对归约口径后来被改写的事实。

若把轨迹压成一句判据：好的复杂性贡献，是让「难」从形容词变成可传递的关系。SAT 只是第一个锚点。锚点一旦钉住，图论、调度、密码学、人工智能里的搜索问题才开始能够互相翻译。库克给出了锚；社区用五十年把地图画大。地图上最大的空白仍是那道千禧年问题——但空白已经有了边界，不再是一片没有坐标系的雾。

参考文献#

• Cook, S. A. The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), 1971.
• Cook, S. A. An Overview of Computational Complexity. Communications of the ACM 26(6), 1983, pp. 400–408.（1982 年图灵奖演讲稿）
• Karp, R. M. Reducibility among Combinatorial Problems. In Miller, R. E. & Thatcher, J. W. (eds.), Complexity of Computer Computations. Plenum, 1972.
• Levin, L. A. Universal Sequential Search Problems. Problems of Information Transmission 9(3), 1973.（俄文原刊；英译后收入西方文献）
• Cook, S. A. & Reckhow, R. A. The Relative Efficiency of Propositional Proof Systems. Journal of Symbolic Logic 44(1), 1979.
• Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• Haken, A. The Intractability of Resolution. Theoretical Computer Science 39, 1985.
• Cobham, A. The Intrinsic Computational Difficulty of Functions. Logic, Methodology and Philosophy of Science, 1965.
• Edmonds, J. Paths, Trees, and Flowers. Canadian Journal of Mathematics 17, 1965.

延伸阅读#

• Sipser, M. Introduction to the Theory of Computation. 3rd ed., Cengage, 2012.（教材中 NP 完全性与库克–列文的标准叙述）
• Arora, S. & Barak, B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.