資訊 / 電腦科學 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