Levin 1973：通用顺序搜索怎样把 NP 搜索写成一个万能问题

破除误解：万能搜索不是「没有算法」，也不是 1971 年的判定完全性#

第一层误解把标题听成「搜索问题没有算法」，或听成布尔公式、集合覆盖、图同态不可判定。这些任务都有算法：按长度可比较的范围枚举全部候选 $y$，再逐个核对谓词 $A(x,y)$ 即可。列文要给的不是停机意义上的不可能，而是一条关于可比较时间的万能性。可计算性 已经把「有没有手续」写成图灵机能否停机；本页假定手续存在，问的是：若存在任何一个穷举型搜索在可比较时间内解不掉，那么六个经典问题也同样解不掉。把通用搜索听成停机问题，会把 1973 年收进 1936 年。

第二层误解把教材里的标准句提前写进这两页：「列文与库克证明了同一条 SAT 判定定理，只是一个用英文、一个用俄文」。库克一九七一年论文 的对象是判定：公式是否为重言式，归约口径是带神谕的询问机。卡普一九七二年论文 的对象仍是判定：二十一个组合问题的是与否，归约口径是一次确定性多项式映射。列文的对象是搜索：找出证据 $y$，并且归约必须把证据双向译过去。准搜索（квазиперебор）才是「这样的 $y$ 是否存在」，相当于判定版。把 1973 年读成 SAT 判定的俄文副本，会把一次证据翻译收成一次是非题。

第三层误解把「库克–列文」听成同一篇论文的两个署名，或听成这两页已经印出库克那种 $T\times T$ 计算表。短讯只陈述定理与引理，证明没有印出。后来补写的草图才把核对手续编成部分布尔函数或同态实例。印出的金属是定义、六题清单、三条翻译算法、以及「万能」这个词；编译的螺丝钉留在纸外。把后来的命名习惯读回这两页，会把一次存在性宣布收成一部合著。

第四层误解把定理 2 听成「SAT 已经属于多项式时间」，或听成本页就是列文 1986 年的平均情况完全问题。定理 2 说的是：对任意一个穷举型搜索，柯莫哥洛夫–乌斯宾斯基算法类里存在一个求解器，其时间相对所有求解器最优，只差一个常数因子，外加一段与 $|x|$ 可比较的加性项。最优仍可能是指数的。它不把问题送进 $P$。平均情况、分布支配与单向函数是后话，不是 1973 年的封面。

可比较时间、穷举型搜索，以及三条翻译算法#

装置从「可比较」开始。两个函数 $f$ 与 $g$ 可比较，当且仅当存在某个 $k$，使得 $f(n)\le(g(n)+2)^k$ 且 $g(n)\le(f(n)+2)^k$。加 2 是为了让小数值也进得了幂。这是柯莫哥洛夫学派里与多项式同档的尺度，不是后来教材默认的图灵机多项式。算法模型可以取柯莫哥洛夫–乌斯宾斯基算法、图灵机或马尔可夫正规算法；短讯写明选择不实质，因为自然编码给出的码长彼此可比较。$x$ 与 $y$ 都是二进制串。

穷举型搜索（переборная задача）的形状是：给定 $x$，找出某个长度与 $x$ 可比较的 $y$，使得性质 $A(x,y)$ 成立；而 $A$ 本身可由一个运行时间与 $|x|$ 可比较的算法核对。准搜索只问这样的 $y$ 是否存在。用后来的话：核对属于多项式时间的搜索问题，其判定投影就是 $NP$。列文没有使用 $NP$ 这个符号。他用的是莫斯科控制论传统里的「перебор」：亚布洛恩斯基（S. V. Yablonsky）1959 年已把最小接触电路的综合说成算法上的穷举困难，茹拉夫廖夫（Yu. I. Zhuravlev）1962 年把集合论方法写进布尔代数，特拉赫滕布罗特（B. A. Trakhtenbrot）1965 年讨论最优计算与亚布洛恩斯基的频率现象，杰格佳尔（M. I. Degtyar）1969 年论证相对函数图计算时无法消去穷举。短讯把这份口碑收成可检验的万能性，而不是再写一篇「这些题显得很难」。

六题按原文顺序如下。对象都按自然方式编成二进制串。任务 1：给定有限集合的清单，以及一份用 500 元子集做成的覆盖，找出指定基数的子覆盖，或判定它是否存在。常数 500 是编码用的固定宽度，不是应用里的经验阈值。任务 2：表格给定一个部分布尔函数，找出指定规模、在定义域上实现该函数的析取范式，或判定它是否存在。任务 3：判定给定的命题演算公式可推出或可反驳；括号里写明，这等于问布尔公式是否恒等于常数。任务 4：给定两图，找出一个图到另一个图的同态，或判定同态是否存在。任务 5：给定两图，找出一个图到另一个图某一部分上的同构，或判定它是否存在。这是子图同构，不是两个图是否同构那道度数仍开放的判定。任务 6：考虑元素取自 1 到 100 的整数矩阵，并给定哪些数字可在竖直方向相邻、哪些可在水平方向相邻；边界上已填若干数字，要求在遵守相邻条件的前提下把矩阵填满。六题各自带搜索版与准搜索版。清单会生长；短讯说同一方法看来容易推广到多数有趣的穷举题。

归约必须保存证据。设 $A(x,y)$ 与 $B(x,y)$ 分别定义搜索问题 $A$ 与 $B$。称 $A$ 可归约到 $B$，当且仅当存在三个算法 $r(x)$、$p(y)$、$s(y)$，运行时间与参数长度可比较，并且 $A(x,p(y))$ 当且仅当 $B(r(x),y)$，$A(x,y)$ 当且仅当 $B(r(x),s(y))$。从 $A$ 的实例 $x$ 可以造出等价的 $B$ 实例 $r(x)$；$A$ 的证据译成 $B$ 的证据，$B$ 的证据再译回来。这比询问机紧：没有神谕，不能靠翻转极性把互补问题收进同一档。这也比卡普的多一函数多：多一把是映成是，却不必交出证据。列文要的是搜索的翻译。若任何穷举型搜索都可归约到某问题，该问题就叫做万能（универсальная）。

定理 1 把万能性收成下界传递。设 $f(n)$ 单调。若存在任何一个穷举型或准穷举型的大量问题，在参数长度与 $n$ 可比较时不能在少于 $f(n)$ 的时间内解决，则任务 1 至 6 也具有同一性质。证明的想法写在纸上：这六题是万能穷举问题。引理 1 即此陈述。合成是直接的：若其中某一题可在少于 $f$ 的时间内找出证据 $y$，则先算 $r(x)$，再把 $y$ 经 $p$ 送回，就会以可比较的额外开销解开那个被假定为更难的问题。矛盾。短讯明白写出：要证明定理里的那个前提——真的存在一个超级多项式的穷举题——仍然没有人做成；特拉赫滕布罗特与杰格佳尔提供过论据，不是分离。万能性可以在不解决这个前提的情况下建立。用后来的符号，前提就是 $P\ne NP$；六题万能就是它们对 $NP$ 搜索完全。本页不把「存在翻译」写成把口令或协议编进覆盖、同态或填表的步骤。

定理 2 是这两页里库克与卡普都没有的那一枚钉子。在柯莫哥洛夫–乌斯宾斯基算法系统中，对任意穷举型搜索 $A(x,y)$，存在一个算法，其求解时间相对所有求解器最优，只差乘一个常数、再加一段与 $|x|$ 可比较的量。印出的短讯到此停住，不写出交错模拟的日程表。概念上，它断言存在一台通用求解器：把所有候选算法按某种枚举交错起来跑，时间配额随步数增大；若其中一台本可在 $T$ 步内交出合法 $y$，这台通用器也会在常数倍的 $T$ 内交出。常数来自模拟开销，加性项来自配额尚小的开头。它是最优性，不是多项式性。把定理 2 听成已经给出可在车间里缩短墙钟时间的 SAT 求解器，会把一条存在性宣布收成操作单。

文末致谢安德烈·柯莫哥洛夫、鲍里斯·特拉赫滕布罗特、扬尼斯·巴尔兹季尼（Jānis Bārzdiņš）与米哈伊尔·杰格佳尔等人。这是莫斯科讨论班上的短讯，不是 STOC 的八页。西方文献过了数年才充分对照。今日写库克–列文，承认的是同一数学对象被发现了两次：一次写成判定与询问机，一次写成搜索与万能穷举。不是两页短讯有第二作者。

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

它证明了：穷举型搜索里存在万能问题；任务 1 至 6 都是这样的问题。因此，若任何一个穷举题需要至少 $f(n)$ 的时间，这六题也需要。准搜索版把同一档写到判定上。它还证明了：在柯莫哥洛夫–乌斯宾斯基模型里，每个穷举题都有一个只差常数因子的最优求解器。用后来的符号，这就是「存在 $NP$ 搜索完全问题」在 1973 年的原句，外加一条最优搜索器的存在性。编码开销来自三条可比较时间的翻译，不是来自对神谕的自适应询问。

它没有证明任何一个具体问题需要超多项式时间。短讯把这一点写成定理 1 的未证前提，并指向苏联文献里已有的尝试。对角化在带多项式时钟的世界里套不上，相对化障碍是 1975 年的后话，见 P vs NP 的证明障碍；原装神谕构造见 Baker–Gill–Solovay 1975。它也没有采用询问机或多一函数作为定义。库克允许翻转极性，因而重言式与 SAT 可落在同一度数；卡普把是映成是，把 $NP$ 与 $\mathrm{coNP}$ 分开。列文保存证据，对象停在搜索。主编译若把核对编成可满足实例，本来就是多一的；需要分清的是目标语言叫重言式、叫 SAT，还是叫「找出一个 $y$」。

它没有覆盖库克的窗口编码，没有覆盖卡普的二十一题清单，没有覆盖时间层级或空间平方模拟。任务 3 与重言式相邻，但短讯问的是公式是否恒为常数，并且没有神谕。任务 5 是子图同构，不是图同构；后者的度数后来仍开放，前者进入完全档。任务 2 的析取范式极小化属于亚布洛恩斯基传统，不是工业综合手册。定理 2 的最优求解器不是 $P=NP$。1986 年的平均情况完全问题、硬核谓词与单向函数是另一页。稳健性来自翻译的可比较时间，不来自后来的产品。只要核对手续能在可比较时间内完成，新的搜索就可以挂到万能题上；幂次会变，万能这一档不会变。概念证据到此为止。三条算法回答的是「完全性在 1973 年用哪一种搜索归约写下」；六题回答的是「哪些经典穷举与任意搜索同生共死」。两句都不是操作单。

跨域连接#

• 库克一九七一年论文：那一页把非确定性接受计算编译成公式，目标语言首先是重言式，归约是询问机。本页把同一档对象改写成搜索：要的不是「是/否」，而是证据 $y$，并且 $r$、$p$、$s$ 必须把证据送过去再送回来。没有库克的判定钉子，西方后来几乎只用 SAT 当源节点；没有列文的搜索钉子，「完全」仍可能停在是非题上，进不了「把证书交出来」。两页必须叠着读。把列文读成库克的俄文附录，会把保存证据这一年的工作说成重复排印。
• 卡普一九七二年论文：那十九页从 SAT 画出二十个组合判定问题，箭头是多一的，答案同号。本页的六题看起来也像覆盖、范式、同态、填表，但每一题都带着「找出那个对象」。卡普证明日常判定与 SAT 同生共死；列文证明日常搜索与任意穷举同生共死。多一不必交证据，搜索归约必须交。把六题听成二十一题的俄文缩写，会把子覆盖的那一组集合收成「是否存在」的一比特。
• 可计算性：停机问题是递归可枚举集的完全问题；列文把万能穷举写成「短证书可核」这一层里的完全搜索。类比是形状上的，不是证明上的。停机的归约没有可比较时间的时钟；这里的 $r$、$p$、$s$ 必须在与参数长度可比较的时间内写完。可判定与可比较时间内可搜索因此是两层边界。把集合覆盖听成不可判定，会把资源问题收成存在问题。定理 2 的通用求解器也停在这一层：它保证不浪费超过常数倍的时间，不保证时间变成多项式。
• 柯莫哥洛夫复杂度：短讯的算法默认取柯莫哥洛夫–乌斯宾斯基模型，可比较时间用 $(g(n)+2)^k$ 来对齐码长。复杂度页问的是最短描述；本页问的是在该模型里搜索证据要花多少步。描述长度与运行时间不是同一个量，但共享同一套「以算法为尺度」的哲学：对象先被编成串，再问串上的手续。把万能搜索听成「最短程序已经给出覆盖」，会把一次时间最优收成一次描述最优。定理 2 优化的是找出 $y$ 的时间，不是 $y$ 本身的柯莫哥洛夫复杂度。
• 组合数学：任务 1 的子覆盖、任务 2 的指定规模析取范式，本是计数与极值里的日常对象。列文问的不是有多少个子覆盖，而是找出一个指定基数的子覆盖。存在性一旦被写成可核的 $A(x,y)$，就可以被三条算法搬运。组合学里漂亮的双射在这里变成保存证据的翻译：一边的实例与证据被译成另一边的实例与证据，真值不变。把六题听成枚举公式，会把搜索收成计数手册。
• 科学哲学：列文把「这些穷举题看起来一样难」改写成可检验的关系：一个搜索与六题之一同档，当且仅当两边可以互相用可比较时间的 $r$、$p$、$s$ 翻译。经验上的难不再是讨论班口碑，而是一份翻译手续是否存在。证伪万能性需要的不是又一个解得很快的实例，而是一个穷举题不能归约到这六题——在标准假设下这样的题不应存在。科学理论在这里的内容是归约闭包，不是对单个谜题的直觉。把万能听成「电路综合很难所以覆盖很难」，说反了箭头：先有任意搜索都可译入的钉子，后有经典穷举被证明与它同生共死。

参考文献#

• 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. MathSciNet MR 340042。收到日期 1972 年 6 月 7 日。—— 本文对象：穷举型搜索、可比较时间、六题万能性，以及柯莫哥洛夫–乌斯宾斯基模型里的最优求解器。
• 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. —— 判定版完全性与询问机，用以标明列文是邻居不是封面。
• Richard M. Karp, "Reducibility among Combinatorial Problems", in Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. —— 多一归约与二十一个判定问题，用以标明搜索口径不是 1972 年的定义。
• S. V. Yablonsky, "О алгоритмических трудностях синтеза минимальных контактных схем", Проблемы кибернетики 2, Физматгиз, 1959, pp. 75–121. —— 短讯所引，电路综合作为穷举困难的苏联传统。
• Yu. I. Zhuravlev, "Теоретико-множественные методы в алгебре логики", Проблемы кибернетики 8, Физматгиз, 1962, pp. 5–44. —— 短讯所引，布尔代数上的集合论方法。
• B. A. Trakhtenbrot, "Оптимальные вычисления и частотное явление Яблонского", seminar notes, Наука, Siberian Branch, Novosibirsk, 1965, nos. 4–5, pp. 79–93. —— 短讯所引，关于穷举前提的已有论据。
• M. I. Degtyar, "О невозможности элиминации полного перебора при вычислении функций относительно их графиков", Доклады АН СССР 189(4), 1969, pp. 748–751. —— 短讯所引，相对函数图无法消去穷举。
• A. N. Kolmogorov & V. A. Uspensky, "К определению алгоритма", Успехи математических наук 13(4), 1958, pp. 3–28. 英译：American Mathematical Society Translations, Series 2, vol. 29, 1963, pp. 217–245. —— 定理 2 所点名的算法系统。

延伸阅读#

• 与 库克一九七一年论文 对读：判定、询问机、窗口编码在那一页；搜索、证据翻译、两页短讯在本页。
• 与 卡普一九七二年论文 对读：多一箭头搬运是非；本页的 $r$、$p$、$s$ 搬运证据。
• 与 计算复杂性 对读：先看 $P$ 与 $NP$ 的类语言，再看本页如何把搜索完全写成万能穷举。
• 与 可计算性 对读：停机完全性与万能搜索形状相似，可比较时钟能否搬迁是分界。
• 与 P vs NP 的证明障碍 对读：短讯已把超多项式前提留作未证；相对化把这句观察收成定理。
• 与 柯莫哥洛夫复杂度 对读：同一模型里，最短描述与最优搜索时间不是同一个量。