Karp 1972：组合问题之间的可归约性怎样把二十一个问题写成多项式完全

破除误解：完全性不是「旅行商没有算法」，也不是 1971 年的询问机#

第一层误解把标题听成「组合问题没有算法」，或听成旅行商、背包、着色不可判定。这些判定问题都有算法：枚举全部子集、全部着色、全部回路即可。卡普要给的不是停机意义上的不可能，而是一条关于多项式资源的传递关系。若其中任一问题可在确定性多项式时间内判定，则整张图上的问题——进而整个 $NP$——都可在确定性多项式时间内判定。把团或哈密顿回路听成停机问题，会把 1972 年收进 1936 年。

第二层误解把教材里的标准句提前写进这一年：「库克已经用多一归约证明 SAT 是 NP 完全，卡普只是多列了二十个名字」。库克一九七一年论文 的归约口径是带神谕的询问机，也就是后来所称的库克归约（多项式时间图灵归约）。询问机可以多次提问，也可以把答案翻转。卡普把归约收紧为一次确定性多项式时间可计算的函数 $f$，使得 $x$ 属于 $A$ 当且仅当 $f(x)$ 属于 $B$。后来称多一归约或卡普归约。多一箭头不能翻转极性，因而不能把 SAT 与重言式收进同一完全性。把 1972 年读成 1971 年的同一句话，会把一次实例映射收成一台询问机。

第三层误解把「二十一个」听成人类组合难题的封闭清单，或听成卡普发明了 SAT 的困难。源节点是库克已经编译好的可满足性：把非确定性接受计算写成公式，公式可满足当且仅当机器接受。卡普做的是把这枚钉子钉进运筹学与图论的日常语言——整数规划、覆盖、回路、着色、背包、划分、最大割。清单会生长。1979 年加里与约翰逊的目录把同一方法铺成数百条，不是本页封面。本页也不把窗口编码或求解器局部传播写成操作单。

第四层误解把对象听成千禧年问题，或听成卡普与库克是同一篇论文的两个署名，或听成「多项式完全」已经等于今日的 NP 完全一词。卡普用 $P$ 记确定性多项式时间可识别的语言，用 $NP$ 记非确定性多项式时间可识别的语言，并用「多项式完全」称呼那些自身在 $NP$ 中、且 $NP$ 中每个语言都可多项式归约到它的问题。唐纳德·克努斯 1974 年在 SIGACT 通讯里征求术语，「NP 完全」此后才成为通行写法。列文 1973 年的俄文短文谈通用搜索问题，是平行发现。把后来的命名习惯读回这十九页，会把一张归约图收成一部学科史。

多一归约、二十一题，以及从 SAT 伸出的箭头#

装置从两类语言与一种箭头开始。确定性图灵机在输入长度的多项式步内停机并给出是否答案，这样的语言构成 $P$。非确定性图灵机在多项式步内存在一条接受计算，这样的语言构成 $NP$。卡普沿用杰克·埃德蒙兹把多项式时间当作「好算法」尺度的传统，把 $P$ 写成希望停靠的岸，把 $NP$ 写成许多自然组合问题已经停泊的港。多项式归约在本页里是多一的：存在多项式时间可计算的函数 $f$，使得对每个实例 $x$，$x$ 为是当且仅当 $f(x)$ 为是。关系可传递。若 $B$ 属于 $P$ 且 $A$ 可归约到 $B$，则 $A$ 也属于 $P$。因此，只要图上有一个多项式完全问题掉进 $P$，整张图连同 $NP$ 都会掉进 $P$。这些判定问题不是从形式语言课里长出来的。它们本来写在运筹学、图论与整数规划的应用清单上：给任务排期、给集合挑覆盖、给图找回路。卡普的贡献是证明它们并不各自拥有一种私有的难度，而是共享 SAT 的那一档。问题看起来来自不同车间，翻译手续却把车间连成同一条生产线。把「组合」听成「与逻辑无关」，会把这张图从中间撕开。

多一与询问机的差别必须写在箭头上，而不是写在形容词上。库克允许神谕、允许自适应、允许把「是」读成「否」。互补问题因此可以落在同一多项式度数：重言式在 $\mathrm{coNP}$，SAT 在 $NP$，询问机只消翻转一次。卡普的 $f$ 必须把是映成是、把否映成否，中间没有神谕可问。于是 $NP$ 与 $\mathrm{coNP}$ 的完全问题被分开：若某个 $\mathrm{coNP}$ 完全语言可以多一归约到 SAT，则 $NP=\mathrm{coNP}$。标准定义后来采用更严的这一档。主编译把接受计算写成可满足实例，本来就是多一的；库克需要翻转，是因为目标语言叫重言式。卡普从 SAT 起步，不再经过重言式。

二十一题的名单按原文顺序是：可满足性；零一整数规划；团；集合装箱；顶点覆盖；集合覆盖；反馈点集；反馈弧集；有向哈密顿回路；无向哈密顿回路；每子句至多三个文字的可满足性；色数；团覆盖；精确覆盖；击中集；斯坦纳树；三维匹配；背包；作业排序；划分；最大割。第一项来自库克。其余二十项由多一箭头挂上去。卡普给出的是归约存在性与构造要点，不是工业实例的编码手册。本页把箭头画成地图，不把配件拆成攻击步骤。

从 SAT 分出三支主干。一支把子句改写成零一变量上的线性不等式，落到整数规划：每个析取子句变成「至少一个文字为真」的和式约束。一支把文字在子句中的出现做成顶点，仅在不同子句且文字不互补时连边，问是否存在规模等于子句数的团；团再传到集合装箱与顶点覆盖。顶点覆盖继续分出集合覆盖、反馈点集、反馈弧集、有向哈密顿回路；有向哈密顿再传到无向哈密顿。第三支先把长子句拆成每条至多三个文字的 3-SAT，新变量只在相邻片段之间衔接真值。3-SAT 再分四路：到色数，色数的补图陈述即团覆盖；到精确覆盖，再传到击中集、斯坦纳树、三维匹配；到背包，再传到作业排序与划分；以及到最大割。传递性保证：凡可归约到 SAT 的语言，都可沿这些箭头走到名单上的每一项。

卡普名单上的每一项都是判定问题：输入一个实例与一个阈值，回答是或否。旅行商作为求最短回路的优化问题并不在二十一题里；其判定版「是否存在长度不超过 $k$ 的回路」与哈密顿回路同属完全档，优化版的困难由判定版传递而来。搜索版「找出一个团」与判定版多项式等价：有了判定手续，可以沿顶点逐个收缩并询问。本页对象停在判定。把卡普听成已经指出旅行商要走哪条路，会把是非题收成寻路手册。埃德蒙兹的最大匹配属于 $P$，哈密顿回路属于完全档，差别不在「图上选边」，而在局部约束能否被花瓣算法一类多项式手续消掉。

这张图回答的是「哪些日常组合问题与 SAT 同生共死」，不是「怎样把口令或协议写成公式去求解」。每个箭头都是一条确定性的、多项式长的书写手续：读入一个实例，写出另一个实例，是与否保持一致。稀疏性、局部窗口、求解器启发式都不在这十九页里。把归约听成「把难题编码进 SAT 然后调用求解器」，说反了本页的方向：卡普要证明的是组合问题本身已经完全，不需要再经过求解器才能获得身份。

它证明了什么，没有覆盖什么#

它证明了：在多一口径下，上述二十一个判定问题都是多项式完全的。任一问题若属于 $P$，则 $P=NP$。运筹学与图论里一批看起来各说各话的问题——覆盖、回路、着色、背包、划分、最大割——被证明与命题可满足性落在同一档。完全性从此不再是单一公式问题的孤立钉子，而成了一张可以继续生长的图。用后来的符号，这就是「这二十一个问题对 $NP$ 多一完全」在 1972 年的原句。后来教材常把 3-SAT 当作新的源节点，因为几乎所有组合归约都从三个文字的子句画配件；源节点可以换，完全性这一档不变。卡普的做法是从 SAT 单向画出，再靠 SAT 已完全得到每一项完全。箭头的方向是「若汇点容易则源点容易」，不是「先解旅行商再解 SAT」。

它没有证明其中任何一个问题不属于 $P$。卡普把含义写成条件句：若多项式完全问题里有一个可在多项式时间解决，则所有这类问题都可以；经验上它们都显得难，但「显得难」不是分离。对角化在带多项式时钟的世界里套不上，相对化障碍是 1975 年的后话，见 P vs NP 的证明障碍；原装神谕构造见 Baker–Gill–Solovay 1975。电路复杂度 也不是本页对象。它也没有采用询问机作为定义。收紧发生在这一年，不是 1971 年的附录。

它没有覆盖列文，没有覆盖后来的平均情况困难，也没有覆盖线性规划后来进入 $P$ 这件事。列文 1973 年把通用搜索问题写成另一套完全性，西方文献过了数年才充分对照。卡普的完全性是最坏情况的、判定版的。背包与划分的随机实例可以很容易，并不推翻最坏情况的钉子。零一整数规划在名单上；有理数上的线性规划不在名单上，后来被证明属于 $P$，说明「规划」一词不能从整数版偷运到线性版。库克当年不肯写入的素数判定与图同构，卡普也没有强行塞进二十一题：素数判定后来进入了 $P$，图同构的度数仍开放。本页是归约图的证据对象，不提供如何把攻击编码进公式、如何用求解器去拆协议的步骤。

稳健性来自多一箭头的传递，不来自后来的产品。只要计算模型能在多项式时间内完成实例改写，新的组合问题就可以挂到这张图上；多项式次数会变，完全性这一档不会变。3-SAT 成为教科书最常用的源节点，是因为卡普已经把 SAT 收到了每子句三个文字。工业求解器能解开许多带结构的实例，并不把最坏情况的地图作废，那是 SAT 求解 的另一页。概念证据到此为止。多一函数回答的是「完全性在 1972 年用哪一种归约写下」；二十一题回答的是「哪些组合语言与 SAT 同生共死」。两句都不是操作单。

跨域连接#

• 组合数学：计数问有多少个对象，卡普问的是判定——是否存在一个规模为 $k$ 的团、一组精确覆盖、一条哈密顿回路。存在性一旦被写成「是/否」语言，就可以被多一函数搬运。组合学里漂亮的双射在这里变成归约：一边的实例被翻译成另一边的实例，真值不变。极值组合关心最大团或最小覆盖的数值；完全性关心的是，当数值进入输入，判定是否达到该数值已经与 SAT 同档。把二十一题听成枚举公式，会把判定图收成计数手册。
• 图论：团、顶点覆盖、色数、哈密顿回路、最大割，本是图论课上各自独立的章节。卡普把它们收成同一完全性里的不同标签：补图把团变成独立集，着色的补图陈述变成团覆盖，有向回路与无向回路之间隔着一次局部改写。图论供给对象，归约供给对象之间的多项式翻译。欧拉回路有多项式算法，哈密顿回路落在完全档，差别不在「回路」这个词，而在局部约束能否被贪心或匹配消掉。把图论听成已经自带难度排序，会把 1972 年的箭头图说成教科书目录。
• 库克一九七一年论文：那一页提供源节点与询问机度数；本页把源节点改名为 SAT，并把度数收紧成多一。没有库克的编译，卡普没有可以出发的 SAT；没有卡普的箭头，完全性仍停在公式语言里，进不了规划、覆盖与回路。两页必须叠着读：先看见「存在接受计算」怎样变成可满足公式，再看见公式怎样变成团与背包。把卡普读成库克的附录，会把口径收紧这一年的工作说成抄名单。
• 可计算性：停机问题是递归可枚举集的多一完全问题；卡普把 SAT 写成 $NP$ 的多一完全问题。类比是形状上的，不是证明上的。停机的多一归约没有多项式时钟；这里的 $f$ 必须在多项式步内写完。可判定与多项式可判定因此是两层边界。把哈密顿回路听成不可判定，会把资源问题收成存在问题。多一口径在两层里都比图灵归约更严：递归可枚举的多一完全问题不能通过翻转变成它的补，正如 $NP$ 的多一完全问题不能通过翻转变成 $\mathrm{coNP}$ 的完全问题。
• 科学哲学：卡普把「这些组合问题看起来一样难」改写成可检验的关系：一个问题与 SAT 同档，当且仅当两边可以互相多项式多一归约。经验上的难不再是实验室口碑，而是一份改写手续是否存在。证伪完全性需要的不是又一个解得很快的实例，而是一个在 $NP$ 里却不能归约到 SAT 的语言——在标准假设下这样的语言不应存在。科学理论在这里的内容是归约闭包，不是对单个谜题的直觉。把完全性听成「旅行商很难所以 SAT 很难」，说反了箭头：先有公式问题的完全性，后有组合海洋被证明与它同生共死。

参考文献#

• Richard M. Karp, "Reducibility among Combinatorial Problems", in Raymond E. Miller & James W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85–103. DOI: 10.1007/978-1-4684-2001-2_9. —— 本文对象：多项式时间多一归约、多项式完全性，以及从 SAT 出发的二十一个组合问题。
• Stephen A. Cook, "The Complexity of Theorem-Proving Procedures", Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151–158. DOI: 10.1145/800157.805047. —— SAT 作为源节点所依据的编译；用以标明询问机口径与多一口径不是同一句话。
• Jack Edmonds, "Paths, Trees, and Flowers", Canadian Journal of Mathematics 17, 1965, pp. 449–467. DOI: 10.4153/CJM-1965-045-4. —— 把多项式时间当作「好算法」尺度的传统，卡普定义 $P$ 时所沿用。
• Donald E. Knuth, "A terminological proposal", SIGACT News 6(1), 1974, pp. 12–18. DOI: 10.1145/1811129.1811130. —— 「NP 完全」一词通行之前的术语讨论，用以标明卡普原文写的是多项式完全。
• Leonid A. Levin, "Universal Sequential Search Problems", Problemy Peredachi Informatsii 9(3), 1973, pp. 115–116. 英译：Problems of Information Transmission 9(3), 1973, pp. 265–266. —— 平行发现，用以标明列文是邻居不是封面。
• Michael R. Garey & David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. —— 后来把同一方法铺成的目录，用以标明二十一题不是封闭清单。

延伸阅读#

• 与 库克一九七一年论文 对读：先看询问机与窗口编译，再看本页如何把口径收紧并拉出组合海洋。
• 与 计算复杂性 对读：总览页把 $P$、$NP$ 与完全性收成地图；本页提供地图上从 SAT 伸出的第一张组合图。
• 与 斯蒂芬·库克 对读：人物页管完全性之后的证明复杂性与图灵奖；本页停在 1972 年的多一箭头。
• 与 可计算性 对读：停机的多一完全性与 SAT 的多一完全性形状相似，多项式时钟是分界。
• 与 P vs NP 的证明障碍 对读：卡普给出的是条件句，不是分离；相对化说明对角化搬不来。
• 与 SAT 求解 对读：最坏情况完全性与工业实例可解可以叠在同一语言上，不互相取消。