信息 / 计算机科学 1971

定理证明过程的复杂性

斯蒂芬·库克

若能快速解出 SAT，便能快速解出一整片难题的宇宙。

Choose your version

In depth · the introduction

成千上万个著名难题，看上去毫不相干——可库克证明，它们其实暗中是同一个问题；只要攻破其中任何一个，便能一举攻破全部。

核心想法

有些问题，验证起来很容易，解起来却似乎难得要命。你给我一张做好的数独，我一分钟就能核对完；可要从头解出来，却可能耗上半天。计算机科学家把这一族「易于验证、却也许难于求解」的问题，叫作 NP。

库克找到了一个问题——SAT，也就是「能否给这些真 / 假开关设定一组取值，让一个逻辑公式整体为真？」——并证明了一件惊人的事：NP 中的每一个问题，都能被快速地改写成一道 SAT 题。于是，SAT 是这一族里最难的那一个。若哪天有人当真找到了求解 SAT 的快速方法，这方法便会立刻让另外成千上万个难题也一齐变快。像 SAT 这样的问题，被称作 NP 完全的——每一个，都把整族的命运扛在自己肩上。

它是如何诞生的

到 1971 年，计算机已经很快，但一个顽固的模式浮现了出来：对于整整一族族的问题——排程、路由、装箱、解谜——所有已知的方法，在最坏情形下，都归结为「把所有可能性都试一遍」；而随着问题变大，可能性的数目会爆炸式增长。这些问题是当真难，还是人们只是还不够聪明？没人说得清，因为根本没有办法，把一个难题和另一个难题相比较。

斯蒂芬·库克——一位刚从伯克利迁往多伦多大学的年轻理论家——给了这个领域那把缺失的标尺。在 1971 年一次会议上发表的、仅八页的论文里，他定义了「一个问题不比另一个更难」究竟意味着什么，进而证明：可满足性正坐在最顶端——每一个易于验证的问题，都可归约到它。次年，理查德·卡普表明，二十一个著名问题统统属于这同一个顶层；这个想法便如野火般蔓延开来。

它为何重要

在库克之前，「这个问题看起来很难」只是一种感觉。在库克之后，它成了一个你能加以证明的精确论断：只要证明你的问题是 NP 完全的，你就证明了——它若有快速解法，便会一举解开另外一大片至今无人攻克的问题；这是一个强有力的提示，叫你别再去苦寻一个完美的快速算法，转而去找「够用就好」的捷径。而这样的快速解法究竟存不存在——「P 对 NP」——便成了计算机科学的中心未解之谜，如今更悬着一份百万美元的奖金。

一个可以想象的画面

想象一圈巨大的、上了锁的门，外加一则传言：它们共用一把万能钥匙。库克并没有找到那把钥匙——他证明了那则传言是真的：他表明，凡是能打开「SAT 那扇门」的钥匙，就能打开这一圈里的每一扇门。于是，没人需要去一把把地撬开所有锁；整圈门的命运，都系于那一扇万能之门。半个世纪过去，仍无人找到这把钥匙，许多人甚至怀疑它根本不存在——但这些门，依旧被证明牢牢相连。

它的位置

库克的论文，是关于「计算之极限」的一组三部曲里的拱心石。阿兰·图灵（1936）划下了机器「究竟能做与根本不能做」之间的界线；库克则划下了机器「能快速做」与「似乎永远做不完」之间的界线。卡普 1972 年的那份清单，随即用日常的问题填满了库克的那一类；而列昂尼德·列文，在苏联独立地抵达了同一个想法——这正是我们称之为「库克–列文定理」的缘由。每当你的手机在安排任务、为地图规划路线，或你的银行笃信「破解它的加密慢得不值一试」时，你都正活在库克所测绘的那片版图之中。

The original document

Original source text

摘要

Stephen A. Cook · The Complexity of Theorem-Proving Procedures · STOC 1971, pp. 151–158

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.

Here “reduced” means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.

P-可归约性

§1 · Tautologies and Polynomial Re-Reducibility

The set of tautologies (denoted by {tautologies}) is a certain recursive set of strings on this alphabet, and we are interested in the problem of finding a good lower bound on its possible recognition times. We provide no such lower bound here, but theorem 1 will give evidence that {tautologies} is a difficult set to recognize, since many apparently difficult problems can be reduced to determining tautologyhood.

Definition. A set S of strings is P-reducible (P for polynomial) to a set T of strings iff there is some query machine M and a polynomial Q(n) such that for each input string w, the T-computation of M with input w halts within Q(|w|) steps (|w| is the length of w) and ends in an accepting state iff w ∈ S.

定理一（及其推论）

§1 · The reduction of every NP problem to satisfiability

Theorem 1. If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.

Corollary. Each of the sets in definitions 1)–5) is P-reducible to {DNF tautologies}.

Proof of the theorem. Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a proposition formula A(w) in conjunctive normal form such that A(w) is satisfiable iff M accepts w. Thus ¬A(w) is easily put in disjunctive normal form (using De Morgan’s laws), and ¬A(w) is a tautology if and only if w ∉ S. Since the whole construction can be carried out in time bounded by a polynomial in |w| (the length of w), the theorem will be proved.

定理二——等价的诸问题

§1 · A first class of problems all equally hard

Theorem 2. The following sets are P-reducible to each other in pairs (and hence each has the same polynomial degree of difficulty): {tautologies}, {DNF tautologies}, D3, {subgraph pairs}.

Remark. We have not been able to add either {primes} or {isomorphic graphpairs} to the above list. To show {tautologies} is P-reducible to {primes} would seem to require some deep results in number theory, while showing {tautologies} is P-reducible to {isomorphic graphpairs} would probably upset a conjecture of Corneil’s from which he deduces that the graph isomorphism problem can be solved in polynomial time.

讨论

§2 · Why this matters

Theorem 1 and its corollary give strong evidence that it is not easy to determine whether a given proposition formula is a tautology, even if the formula is in normal disjunctive form. Theorems 1 and 2 together suggest that it is fruitless to search for a polynomial decision procedure for the subgraph problem, since success would bring polynomial decision procedures to many other apparently intractible problems.

Furthermore, the theorems suggest that {tautologies} is a good candidate for an interesting set not in L*, and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.

Stephen A. Cook · University of Toronto · 1971