圖靈獎演講：組合學、複雜性與隨機性 1985 年圖靈獎得主闡述了他對這個領域發展的觀點，該領域現已被稱為理論計算機科學。 RICHARD M. KARP 本次演講獻給我父親 Abraham Louis Karp 的回憶。

我很榮幸也很高興能獲得今年的圖靈獎。儘管獲得這樣的認可令人滿足，但我發現作為一名研究人員，我最大的滿足感來自於研究本身，以及我在這條路上建立的友誼。我想和大家一起漫步我的 25 年研究生涯，探索組合演算法 (combinatorial algorithms) 和計算複雜性 (computational complexity) 領域，並告訴你們一些對我來說顯得重要的概念，以及一些啟發和影響過我的人。

開端 (BEGINNINGS)

我進入計算機領域相當偶然。1955 年從 Harvard College 數學系畢業後，我面臨著下一步該做什麼的決定。謀生對我吸引力不大，因此研究所是顯而易見的選擇。一個可能性是追求數學事業，但當時這個領域正處於強調抽象和普遍性的鼎盛時期，而我最喜歡的具體和應用數學似乎已不受歡迎。

因此，我幾乎是在別無選擇的情況下，進入了 Harvard Computation Laboratory 的博士學位課程。當時，許多後來成為計算機科學課程核心的課題甚至還沒被想到，所以我選修了各種各樣的課程：交換理論 (switching theory)、數值分析 (numerical analysis)、應用數學、機率與統計 (probability and statistics)、作業研究 (operations research)、電子學和數理語言學 (mathematical linguistics)。雖然課程在深度和連貫性方面有很多不足之處，但當時瀰漫著一種非常特別的氛圍；我們知道我們正在見證一個以計算機為中心的新科學學科的誕生。我發現我在演算法的結構中找到了美感和優雅，並且我對構成計算機與計算研究基礎的離散數學有天賦。簡而言之，我或多或少地偶然闖入了一個我非常喜歡的領域。

簡單與困難的組合問題 (EASY AND HARD COMBINATORIAL PROBLEMS)

從那些早期開始，我一直對組合搜索問題抱有特殊的興趣——這些問題可以比作拼圖遊戲，人們必須以特定的方式組合結構的各個部分。這類問題涉及在有限但極其龐大的、有結構的可能解、模式或排列集合中進行搜索，以找到一個滿足既定條件的解。這類問題的一些例子包括積體電路晶片上元件的佈局和互連、美國國家橄欖球聯盟 (National Football League) 的賽程安排，以及校車車隊的路線規劃。

在這些組合難題中的任何一個內部，都潛藏著組合爆炸 (combinatorial explosion) 的可能性。由於必須搜索的可能數量龐大且急劇增長，除非在搜索可能解的空間時運用一些精妙的技巧，否則可能會遇到海量的計算。我想從告訴你們一些我第一次遭遇組合爆炸的經歷開始本次演講的技術部分。

我第一次敗給這種現象是在 1959 年加入 IBM Yorktown Heights Research Center 後不久。我被分配到一個由 J. P. Roth 領導的小組，他是一位傑出的代數拓撲學家 (algebraic topologist)，在交換理論方面做出了顯著貢獻。我們小組的任務是創建一個用於自動合成交換電路的計算機程式。程式的輸入是一組布林公式 (Boolean formulas)，規定電路的輸出如何依賴於輸入；程式應該生成一個使用最少邏輯閘 (logic gates) 的電路來完成這項工作。圖 1 顯示了一個三變數多數函數的電路；當三個變數 x, y 和 z 中至少有兩個為高時，輸出為高。

FIGURE 1. A Circuit for the Majority Function 圖 1. 多數函數電路

(示意圖顯示了一個包含 AND 和 OR 邏輯閘的電路，實現了三變數的多數函數。)

我們設計的程式包含許多巧妙的捷徑和改進，但其基本機制只是按成本遞增的順序列舉可能的電路。隨著輸入變數數量的增加，程式必須梳理的電路數量急劇增長，因此，我們永遠無法解決玩具問題之外的問題。今天，我們甚至嘗試列舉方法的樂觀態度可能顯得完全天真，但我們不是唯一一個陷入這個陷阱的人；過去二十年自動定理證明 (automatic theorem proving) 的許多工作，都是從玩具問題成功解決後的最初興奮開始，接著是組合爆炸現象的嚴重性完全顯現後的幻滅。

大約在同一時期，我開始與 IBM 的 Michael Held 一起研究旅行銷售員問題 (traveling salesman problem)。這個問題得名於一位銷售員的情境，他希望拜訪其轄區內的所有城市，從家鄉城市開始並結束，同時使他的總旅行成本最小化。在城市是平面上的點且旅行成本等同於歐幾里得距離 (Euclidean distance) 的特殊情況下，這個問題就是找到一個通過所有城市且周長最小的多邊形（見圖 2）。幾年前，Rand Corporation 的 George Dantzig, Raymond Fulkerson 和 Selmer Johnson 結合手動和自動計算，成功解決了一個 49 個城市的問題，我們希望打破他們的記錄。

FIGURE 2. A Traveling Salesman Tour 圖 2. 一條旅行銷售員路線

(示意圖顯示了連接平面上一組點的一條閉合路線。)

儘管外觀無害，旅行銷售員問題潛藏著組合爆炸的可能性，因為通過平面上 n 個城市的可能路線數是 (n - 1)!/2，這是 n 的一個增長非常快的函數。例如，當城市數只有 20 個時，以每秒一百萬條路線的速度暴力列舉所有可能的路線所需的時間將超過一千年。

Held 和我嘗試了多種解決旅行銷售員問題的方法。我們首先重新發現了一種基於動態規劃 (dynamic programming) 的捷徑，該捷徑最初由 Richard Bellman 指出。動態規劃方法將搜索時間縮短到 n2^n，但這個函數也呈爆炸性增長，該方法在實踐中僅限於最多 16 個城市的問題。有一段時間，我們放棄了精確求解問題的想法，並嘗試了傾向於產生良好但不一定最優路線的局部搜索方法 (local search methods)。使用這些方法，首先從一條隨機路線開始，並重複尋找可以改進它的局部變化。這個過程一直持續到找到一條不能再通過任何此類局部變化改進的路線為止。

我們的局部改進方法相當笨拙，Bell Labs 的 Shen Lin 和 Brian Kernighan 後來找到了更好的方法。如果不需要嚴格的最優解，這些快速而粗略的方法在實踐中通常非常有用，但人們永遠無法保證它們的表現如何。

接著我們開始研究分支定界法 (branch-and-bound methods)。這類方法本質上是列舉性的，但它們通過修剪掉可能解空間的大部分來提高效率。這是通過計算包含某些連結但不包含其他連結的每條路線的成本下界來實現的；如果下界足夠大，則可以得出結論，沒有這樣的路線可能是最優的。經過一系列長時間的失敗實驗後，Held 和我偶然發現了一種計算下界的強大方法。這種定界技術使我們能夠嚴格地修剪搜索範圍，從而能夠解決多達 65 個城市的問題。我認為我的任何理論結果都沒有像 Held 和我在第一次測試我們的定界方法那個晚上，看到計算機輸出數字的景象那樣令人興奮。

後來我們發現我們的方法是稱為 Lagrangian relaxation 的舊技術的一種變體，這種技術現在在分支定界法中常規用於構造下界。有一段時間，我們的程式是旅行銷售員問題的世界冠軍求解器，但如今存在更令人印象深刻的程式。它們基於一種稱為多面體組合學 (polyhedral combinatorics) 的技術，該技術試圖將旅行銷售員問題的實例轉換為非常大的線性規劃問題。這些方法可以解決 300 多個城市的問題，但這種方法並不能完全消除組合爆炸，因為解決問題所需的時間仍然隨著城市數量的增加呈指數增長。

旅行銷售員問題仍然是一個引人入勝的謎團。最近出版了一本 400 多頁的書，涵蓋了對這個難解問題的大部分已知知識。稍後，我們將討論 NP 完備性 (NP-completeness) 理論，該理論提供的證據表明旅行銷售員問題本身是難以處理的 (intractable)，因此再巧妙的演算法設計也無法完全克服這個問題內部潛藏的組合爆炸可能性。

組合最佳化與計算複雜性理論的發展 (The Development of Combinatorial Optimization and Computational Complexity Theory)

以下是組合最佳化與計算複雜性理論發展的時間線：

年份 事件
1900 希爾伯特的基礎問題：數學是否完備、一致且可判定？ 希爾伯特第十問題：是否存在求解丟番圖方程的通用判定程序？ (Hilbert's fundamental questions: Is mathematics complete, consistent, and decidable? Hilbert's 10th Problem: Are there general decision procedures for Diophantine equations?)
1930s 可計算性先驅。 (Computability pioneers.)
1937 Turing 引入數位計算機的抽象模型，並證明停機問題和一階邏輯的判定問題不可判定。 (Turing introduces abstract model of digital computer, and proves undecidability of Halting Problem and decision problem for first-order logic.)
1947 Dantzig 發明線性規劃問題的單純形法。 (Dantzig devises simplex method for linear programming problem.)
1957 Ford 和 Fulkerson 等人提出解決網路流問題的有效演算法。 (Ford and Fulkerson et al. give efficient algorithms for solving network flow problems.)
1959 Rabin, McNaughton, Yamada：計算複雜性理論的初步跡象。 (Rabin, McNaughton, Yamada: First glimmerings of computational complexity theory.)
1965 Hartmanis 和 Stearns 定義「複雜性」——引入使用抽象機器的計算複雜性框架——獲得關於複雜性類別結構的結果。 ("Complexity" defined by Hartmanis and Stearns--introduce framework for computational complexity using abstract machines--obtain results about structure of complexity classes.)
Edmonds 將「好」演算法定義為其運行時間受到輸入大小的多項式函數限制的演算法。為匹配問題找到了這樣的演算法。 (Edmonds defines "good" algorithm as one with running time bounded by polynomial function the size of input. Found such an algorithm for Matching Problem.)
1970s 基於成本比率上界的近似最優解搜索。 (Search for near-optimal solutions based on upper bound on cost ratio.)
1971 基於 Davis, Robinson 和 Putman 的工作，Matiyasevic 解決了希爾伯特第十問題：不存在求解丟番圖方程的通用判定程序。 (Building on work of Davis, Robinson, and Putman, Matiyasevic solves Hilbert's 10th: No general decision procedure exists for solving Diophantine equations.)
Cook 定理：所有 NP 問題都可在多項式時間內歸約到可滿足性問題。Levin 也發現了這個原理。 (Cook's Theorem: All NP Problems polynomial-time reducible to Satisfiability Problem. Levin also discovers this principle.)
1972 Karp 使用多項式時間歸約證明了 21 個打包、匹配、覆蓋等問題是 NP 完備的。 (Karp uses polynomial-time reducibility to show that 21 problems of packing, matching, covering, etc., are NP-complete.)
1973 Meyer, Stockmeyer 等人證明了邏輯和自動機理論中某些判定問題的難處理性。 (Meyer, Stockmeyer et al. prove intractability of certain decision problems in logic and automata theory.)
1975 Karp 脫離最壞情況範式，研究組合演算法的機率分析。 (Karp departs from worst-case paradigm and investigates probabilistic analysis of combinatorial algorithms.)
1976 Rabin 等人開啟了隨機演算法的研究。 (Rabin et al. launch study of randomized algorithms.)
1980 Borgwardt, Smale 等人對單純形法進行機率分析。 (Borgwardt, Smale et al. conduct probabilistic analysis of simplex algorithm.)
1984 Karmarkar 設計出理論上高效且實用的線性規劃演算法。 (Karmarkar devises theoretically efficient and practical linear programming algorithm.)

在那些早期，我在 IBM Research Laboratory at Yorktown Heights 受益於一群傑出的組合數學家，在他們的指導下，我學會了在不遭遇組合爆炸的情況下解決某些組合問題的重要技術。例如，我熟悉了 Dantzig 著名的用於線性規劃問題的單純形法 (simplex algorithm)。線性規劃問題是在高維空間的多面體 (polyhedron) 上找到離給定外部超平面 (hyperplane) 最近的點（多面體是二維空間多邊形或三維空間普通多面體的推廣，超平面是平面中直線或三維空間中平面的推廣）。離超平面最近的點總是多面體的角點或頂點（見圖 3）。在實踐中，單純形法可以依賴於非常快速地找到所需的頂點。

FIGURE 3. The Linear Programming Problem 圖 3. 線性規劃問題

(示意圖顯示了一個多面體和一個外部超平面，指出多面體上離超平面最近的點是頂點。)

我還學習了 Lester Ford 和 Fulkerson 美麗的網路流理論 (network flow theory)。該理論關注的是商品（如石油、天然氣、電力或資訊位元）通過網路輸送的速率，其中每條連結都有一個限制其傳輸商品速率的容量。許多乍看之下與商品通過網路流動無關的組合問題，都可以重新表述為網路流問題，並且該理論能夠優雅高效地解決這些問題，除了加法和減法之外不使用任何算術運算。

讓我通過略述用於解決被稱為婚姻問題 (marriage problem) 的組合最佳化問題的所謂匈牙利演算法 (Hungarian algorithm) 來闡明這個美麗的理論。這個問題涉及一個由 n 個男人和 n 個女人組成的社會。問題是以最低成本將男人和女人一對一配對，其中每個配對都賦予一個給定的成本。這些成本由一個 n x n 矩陣給出，其中每一行對應一個男人，每一列對應一個女人。通常，n 個男人與 n 個女人的每個配對都對應於從矩陣中選擇 n 個條目，其中任意兩個條目不在同一行或同一列；配對的成本是所選 n 個條目的總和。可能的配對數量是 n!，這是一個增長如此迅速的函數，以至於暴力列舉幾乎沒有用處。圖 4a 顯示了一個 3 x 3 的例子，我們可以看到男人 3 與女人 2 配對的成本等於 9，即給定矩陣第三行第二列的條目。

FIGURE 4. An Instance of the Marriage Problem 圖 4. 婚姻問題的一個實例

(示意圖顯示了一個 3x3 的成本矩陣，並逐步轉換以找到零成本配對。) (a) 原始成本矩陣 (Original cost matrix) (b) 從每行減去最小條目 (Subtract least entry from each row) (c) 從沒有零的列減去最小條目 (Subtract least entry from columns without a zero) (d) 調整行/列以創建更多零，並標示出一個成本為零的完整配對 (Adjust rows/columns to create more zeros, showing a complete pairing with zero cost marked by circles)

匈牙利演算法背後的關鍵觀察是，如果從矩陣的某一行或某一列的所有條目中減去同一個常數，問題保持不變。利用這種改變矩陣的自由度，演算法試圖創建一個所有條目都非負的矩陣，使得每個完整配對都有一個非負的總成本，並且其中存在一個所有條目都為零的完整配對。這樣一個配對顯然對於創建的成本矩陣是最優的，並且對於原始成本矩陣也是最優的。在我們的 3 x 3 例子中，演算法首先從每行中減去最小的條目，從而創建一個每行至少包含一個零的矩陣（圖 4b）。然後，為了在每一列中創建一個零，演算法從尚未包含零的每一列的所有條目中減去該列的最小條目（圖 4c）。在這個例子中，結果矩陣中的所有零都位於第一行或第三列；由於一個完整配對只包含每行或每列的一個條目，因此尚不可能找到一個完全由零條目組成的完整配對。為了創建這樣一個配對，需要在矩陣的左下部分創建一個零。在這種情況下，演算法通過從第一列和第二列中減去 1 並向第一行加上 1 來創建這樣一個零（圖 4d）。在結果的非負矩陣中，三個被圈起來的條目給出了一個成本為零的完整配對，因此這個配對在最終矩陣和原始矩陣中都是最優的。

這個演算法比暴力列舉要巧妙得多，效率也高得多。它解決婚姻問題所需的時間僅隨矩陣行數和列數 n 的三次方增長，因此，可以解決具有數千行和數千列的實例。

創建線性規劃理論和網路流理論的研究人員對計算複雜性問題持務實態度：如果演算法在實踐中運行得足夠快，就被認為是有效的，證明它在所有可能情況下都很快並非特別重要。1967 年，我注意到解決某些網路流問題的標準演算法存在一個理論缺陷，這導致它在某些人為構造的例子上運行得非常慢。我發現糾正這個缺陷並不困難，並在 Princeton 的組合學研討會上就我的結果做了一次演講。Princeton 的人告訴我，National Bureau of Standards 的研究員 Jack Edmonds 在前一周的同一研討會上發表了非常相似的結果。

由於這次巧合，Edmonds 和我開始一起研究網路流演算法的理論效率，並適時地發表了一篇聯合論文。但我們合作的主要影響是加強了我當時已經摸索的一些關於計算複雜性的想法，這些想法對我未來的研究方向產生了強大影響。Edmonds 是一位出色的匠人，他利用與線性規劃相關的思想為許多組合問題開發了令人驚嘆的演算法。但是，除了構建演算法的技巧外，他在另一個重要方面也領先於同時代的人：他對演算法的效率有了清晰精確的理解。他的論文闡述了這樣一個觀點：如果演算法的運行時間受到輸入大小的多項式函數限制，而不是指數函數限制，那麼就應該被認為是「好的」。例如，根據 Edmonds 的概念，解決婚姻問題的匈牙利演算法是一個好的演算法，因為其運行時間隨輸入大小的三次方增長。但據我們所知，旅行銷售員問題可能沒有好的演算法，因為我們嘗試過的所有演算法的運行時間都隨著問題規模的增加而呈指數增長。Edmonds 的定義使我們對如何界定簡單組合問題和困難組合問題有了清晰的概念，並且至少在我看來，首次開闢了我們將來可能提出一個定理，證明或證偽旅行銷售員問題本身是否難以處理的可能性。

通往 NP 完備性之路 (The Road to NP-Completeness)

隨著組合演算法領域的發展，1960 年代期間另一股主要的研究潮流正在匯聚力量——計算複雜性理論 (computational complexity theory)。這門學科的基礎由一群邏輯學家在 1930 年代奠定，其中包括 Alan Turing，他們關注的是判定數學陳述真偽的自動程序的存在或不存在。

Turing 和其他可計算性理論 (computability theory) 的先驅者首先證明了某些定義明確的數學問題是不可判定的 (undecidable)，也就是說，原則上不可能存在能夠解決這類問題所有實例的演算法。這類問題的第一個例子是停機問題 (Halting Problem)，這實質上是一個關於計算機程式除錯的問題。停機問題的輸入是一個計算機程式及其輸入數據；問題是判斷該程式最終是否會停止。為什麼對於這樣一個定義明確的問題會沒有演算法呢？困難在於存在無限搜索的可能性。顯而易見的解決方法是簡單地運行程式直到它停止。但是到什麼時候放棄，判斷程式不會停止才是合理的呢？似乎沒有辦法為所需的搜索量設定一個限制。Turing 使用一種稱為對角線法 (diagonalization) 的技術構建了一個證明，表明不存在能夠成功處理停機問題所有實例的演算法。

多年來，幾乎在數學的每個分支中都發現了不可判定的問題。數論中的一個例子是求解丟番圖方程 (Diophantine equations) 的問題：給定一個多項式方程，例如 4xy^2 + 2xy^2z^3 - 11x^3y^2z^2 = -1164，是否存在整數解？尋找求解此類丟番圖方程的通用判定程序的問題，最初由 David Hilbert 於 1900 年提出，後來被稱為希爾伯特第十問題 (Hilbert's Tenth Problem)。這個問題一直懸而未決，直到 1971 年，證明了不存在這樣的判定程序。

劃分可解問題和不可解問題邊界的基本工具之一是歸約性 (reducibility) 的概念，這個概念首先通過邏輯學家 Emil Post 的工作得到突出。如果給定一個能夠解決問題 B 的副程序，就可以構造一個演算法來解決問題 A，那麼問題 A 就被稱為可歸約到問題 B。例如，一個里程碑式的結果是停機問題可歸約到希爾伯特第十問題（見圖 5）。由此可知，希爾伯特第十問題必然是不可判定的，因為否則我們就可以利用這種歸約來導出一個解決停機問題的演算法，而停機問題是已知不可判定的。當我們討論 NP 完備性和 P : NP 問題時，歸約性的概念將再次出現。

FIGURE 5. The Halting Problem Is Reducible to Hilbert's Tenth Problem 圖 5. 停機問題可歸約到希爾伯特第十問題

(示意圖顯示了一個從停機問題實例通過轉換副程序到希爾伯特第十問題實例的流程。)

複雜性理論從可計算性理論繼承的另一個重要主題是解決問題的能力與檢查解決方案的能力之間的區別。即使沒有找到丟番圖方程解的通用方法，檢查一個提議的解卻很容易。例如，要檢查 x = 3, y = 2, z = -1 是否構成上述丟番圖方程的解，只需代入給定值並進行一些算術運算即可。正如我們稍後將看到的，解決與檢查之間的區別正是 P : NP 問題的核心所在。

理論計算機科學一些最經久不衰的分支，其起源於可計算性理論的抽象機器 (abstract machines) 及其他形式體系。其中一個最重要的分支是計算複雜性理論。複雜性理論不再僅僅詢問一個問題是否可判定，而是詢問解決這個問題有多困難。換句話說，複雜性理論關注的是當對 Turing 機 (Turing machine) 等通用計算設備的執行時間或可能使用的記憶體量施加限制時，它們的能力。複雜性理論的初步跡象可以在 Michael Rabin 以及 Robert McNaughton 和 Hideo Yamada 於 1959 年和 1960 年發表的論文中找到，但正是 Juris Hartmanis 和 Richard Stearns 於 1965 年發表的論文標誌著現代複雜性理論的開始。Hartmanis 和 Stearns 使用 Turing 機作為其抽象計算機模型，為由在輸入長度 n 的某個給定函數所界定的步數內可解決的所有問題組成的「複雜性類別」 (complexity class) 提供了精確定義。他們借鑒了 Turing 用來證明停機問題不可判定的對角線法技術，證明了關於複雜性類別結構的許多有趣結果。我們所有閱讀了他們論文的人都無法不意識到，我們現在有了一個令人滿意的形式框架，可以追問 Edmonds 早先以直觀方式提出的問題——例如，旅行銷售員問題是否能在多項式時間內解決的問題。

同年，我從 Hartley Rogers 的一本極好的書中學習了可計算性理論，他曾是我的 Harvard 老師。我記得當時我曾思考，可計算性理論中如此核心的歸約性概念是否也能在複雜性理論中發揮作用，但我不知道如何建立聯繫。大約在同一時期，即將在 1976 年獲得 Turing Award 的 Michael Rabin，當時在 Jerusalem 的 Hebrew University 休假，作為訪客在 IBM Research Laboratory at Yorktown Heights 工作。我們恰巧住在 New York City 郊區的同一棟公寓樓裡，於是養成了共乘前往 Yorktown Heights 的習慣。Rabin 是一位極富原創性的思想家，也是自動機理論 (automata theory) 和複雜性理論的創始人之一，通過我在 Sawmill River Parkway 沿途與他的日常討論，我對邏輯學、可計算性理論和抽象計算機理論有了更廣泛的視角。

1968 年，或許受到席捲全國的普遍社會動盪的影響，我決定搬到 University of California at Berkeley，那裡是行動發生的地方。在 IBM 的歲月對我作為一個科學家的發展至關重要。與 Alan Hoffman, Raymond Miller, Arnold Rosenberg, 和 Shmuel Winograd 等傑出科學家合作的機會簡直無價。我的新同事圈子包括 Michael Harrison，一位招募我到 Berkeley 的傑出語言理論家，Eugene Lawler，一位組合最佳化專家，Manuel Blum，一位複雜性理論創始人，後來在數論和密碼學的交叉領域做出了傑出工作，以及 Stephen Cook，他的複雜性理論工作幾年後對我產生了巨大影響。在數學系，有 Julia Robinson，她在希爾伯特第十問題上的工作很快就會開花結果，Robert Solovay，一位著名的邏輯學家，後來發現了一種用於測試數字是否為素數的重要隨機演算法，以及 Steve Smale，他在線性規劃演算法的機率分析方面開創性的工作在幾年後影響了我。而在海灣對岸的 Stanford，有線性規劃之父 Dantzig，創立了數據結構 (data structures) 和演算法分析 (analysis of algorithms) 領域的 Donald Knuth，還有當時還是研究生的 Robert Tarjan，以及來自 Cornell 的休假訪客 John Hopcroft，他們傑出地將數據結構技術應用於圖演算法 (graph algorithms) 的分析。

1971 年，當時已移居 University of Toronto 的 Cook，發表了他具有歷史意義的論文「論定理證明程序的複雜性」(On the Complexity of Theorem-Proving Procedures)。Cook 討論了我們現在稱為 P 和 NP 的問題類別，並引入了我們現在稱為 NP 完備性 (NP-completeness) 的概念。非正式地說，P 類別包含所有可以在多項式時間內解決的問題。因此，婚姻問題屬於 P 類別，因為匈牙利演算法在大約 n^3 步內解決了規模為 n 的實例，但旅行銷售員問題似乎不屬於 P 類別，因為所有已知的解決方法都需要指數時間。如果我們接受這樣一個前提，即一個計算問題除非存在多項式時間演算法來解決，否則它就不是可處理的 (tractable)，那麼所有可處理的問題都屬於 P 類別。NP 類別包含所有那些提議的解決方案可以在多項式時間內檢查的問題。例如，考慮旅行銷售員問題的一個版本，其中輸入數據包括所有城市對之間的距離，以及一個「目標數字」 T，任務是判斷是否存在一條長度小於或等於 T 的路線。判斷這樣一條路線是否存在似乎極其困難，但如果給我們一條提議的路線，我們可以很容易地檢查其長度是否小於或等於 T；因此，這個版本的旅行銷售員問題屬於 NP 類別。類似地，通過引入目標數字 T 的方法，所有通常在商業、科學和工程領域考慮的組合最佳化問題都有屬於 NP 類別的版本。

因此，NP 是組合問題通常落入的領域；在 NP 之內是 P，即具有高效解決方案的問題類別。一個基本問題是，類別 P 與類別 NP 之間的關係是什麼？很明顯，P 是 NP 的子集，而 Cook 引人關注的問題是 P 和 NP 是否可能是同一個類別。如果 P 等於 NP，將會產生令人震驚的後果：這將意味著每一個容易檢查其解決方案的問題，也將容易解決；這將意味著，每當一個定理有一個簡短的證明時，一個統一的程序就能夠快速找到該證明；這將意味著所有常見的組合最佳化問題都將在多項式時間內解決。簡而言之，這將意味著組合爆炸的詛咒可以被根除。但是，儘管有所有這些啟發性證據表明如果 P 和 NP 相等將是好得令人難以置信的事情，至今仍未找到證明 P ≠ NP 的證據，一些專家甚至認為永遠找不到證明。

Cook 論文最重要的成就是證明了 P = NP 當且僅當一個稱為可滿足性問題 (Satisfiability Problem) 的特定計算問題屬於 P。可滿足性問題來自數學邏輯，並在交換理論中有應用，但它可以被描述為一個簡單的組合難題：給定幾個由大寫和小寫字母組成的序列，是否可能從每個序列中選擇一個字母，而不選擇任何字母的大寫和小寫版本？例如，如果序列是 Abc, BC, aB, 和 ac，可以從第一個序列中選擇 A，從第二個和第三個序列中選擇 B，從第四個序列中選擇 c；注意同一個字母可以被選擇不止一次，只要我們不選擇其大寫和小寫版本即可。無法做出所需選擇的一個例子是給定的四個序列 AB, Ab, aB, 和 ab。

可滿足性問題明顯屬於 NP 類別，因為檢查一個提議的字母選擇是否滿足問題條件很容易。Cook 證明了，如果可滿足性問題可以在多項式時間內解決，那麼 NP 中的每個問題都可以在多項式時間內解決，因此 P = NP。因此我們看到，這個看似奇特且無關緊要的問題是一個典型的組合問題；它掌握著高效解決所有 NP 問題的關鍵。

Cook 的證明基於我們之前在討論可計算性理論時遇到的歸約性概念。他證明了 NP 中的任何問題實例都可以轉換為可滿足性問題的一個對應實例，其方式是原始問題有解當且僅當可滿足性實例有解。此外，這種轉換可以在多項式時間內完成。換句話說，可滿足性問題足夠通用，可以捕捉 NP 中任何問題的結構。由此可知，如果我們可以在多項式時間內解決可滿足性問題，那麼我們就可以構造一個多項式時間演算法來解決 NP 中的任何問題。這個演算法將由兩部分組成：一個將給定問題實例轉換為可滿足性問題實例的多項式時間轉換程序，以及一個解決可滿足性問題本身的副程序（見圖 6）。

FIGURE 6. The Traveling Salesman Problem Is Polynomial-Time Reducible to the Satisfiability Problem 圖 6. 旅行銷售員問題可在多項式時間內歸約到可滿足性問題

(示意圖顯示了一個從旅行銷售員問題實例通過轉換副程序到可滿足性問題實例的流程。)

讀了 Cook 的論文後，我立刻意識到他的「典型組合問題」概念，是對長期以來一直是組合最佳化領域傳說一部分的想法的形式化。該領域的研究人員知道，整數規劃問題 (integer programming problem)（實質上是判斷一組線性不等式是否存在整數解的問題）足夠通用，可以表達任何常見組合最佳化問題的約束條件。Dantzig 曾在 1960 年發表過關於這個主題的論文。由於 Cook 對定理證明而不是組合最佳化感興趣，他選擇了一個不同的典型問題，但基本思想是相同的。然而，存在一個關鍵區別：通過使用複雜性理論的工具，Cook 創建了一個框架，在這個框架內，一個給定問題的典型性可以成為一個定理，而不是一個非正式的論斷。有趣的是，當時在列寧格勒，現任 Boston University 教授的 Leonid Levin，獨立地發現了基本上相同的思想集合。他的典型問題與用多米諾骨牌鋪滿平面有限區域有關。

我決定研究某些長期以來被認為是難以處理的經典組合問題，是否也具有 Cook 意義上的典型性。我將這類問題稱為「polynomial complete」，但這個術語後來被更精確的術語「NP-complete」取代。一個問題是 NP 完備的 (NP-complete)，如果它屬於 NP 類別，並且 NP 中的每個問題都可以在多項式時間內歸約到它。因此，根據 Cook 定理，可滿足性問題是 NP 完備的。要證明 NP 中的一個給定問題是 NP 完備的，只需要證明某個已知是 NP 完備的問題可以在多項式時間內歸約到給定問題。通過構建一系列多項式時間歸約，我證明了組合最佳化中出現的大多數經典問題，如打包、覆蓋、匹配、分割、路由和排程等，都是 NP 完備的。我在 1972 年的一篇題為「組合問題之間的歸約性」 (Reducibility among Combinatorial Problems) 的論文中提出了這些結果。我的早期結果很快被其他研究人員改進和擴展，在接下來的幾年中，幾乎在進行計算的每個領域中出現的數百個不同問題，都被證明是 NP 完備的。

應對 NP 完備問題 (Coping with NP-Complete Problems)

我的 NP 完備問題研究得到了獎勵——一個行政職位。從 1973 年到 1975 年，我領導了新成立的 Berkeley 計算機科學部 (Computer Science Division)，我的職責讓我幾乎沒有時間進行研究。結果，我在一個非常活躍的時期成了旁觀者，這段時期發現了許多 NP 完備問題的例子，並且開始了第一次嘗試繞過 NP 完備性負面影響的工作。

1970 年代早期證明的 NP 完備性結果表明，除非 P = NP，否則商業、科學和工程中出現的絕大多數組合最佳化問題都是難以處理的：沒有任何解決方法可以完全避開組合爆炸。那麼，在實踐中我們如何應對這些問題呢？一種可能的方法源於這樣一個事實：接近最優的解決方案通常就足夠好了：一個旅行銷售員可能會對比最優路線長幾個百分點的路線感到滿意。遵循這種方法，研究人員開始尋找能夠保證為 NP 完備組合最佳化問題產生接近最優解的多項式時間演算法。在大多數情況下，近似演算法 (approximation algorithm) 的性能保證以演算法產生的解成本與最優解成本之間比率的上界形式呈現。

一些關於具有性能保證的近似演算法最有趣的工作涉及一維裝箱問題 (one-dimensional bin-packing problem)。在這個問題中，必須將一組不同大小的物品裝入容量相同的箱子中。目標是最小化用於裝箱的箱子數量，同時遵守裝入任何箱子中物品大小總和不得超過箱子容量的約束。在 1970 年代中期，一系列關於裝箱問題近似演算法的論文最終達到了 David Johnson 對首次適應遞減演算法 (first-fit-decreasing algorithm) 的分析。在這個簡單的演算法中，物品按其大小遞減順序考慮，然後依次將每個物品放入第一個可以接受它的箱子中。例如，在圖 7 的例子中，有四個箱子，每個容量為 10，以及八個大小從 2 到 8 的物品。Johnson 表明，這種簡單方法保證能達到最大 2/9 的相對誤差；換句話說，所需箱子數量永遠不會比最優解中的箱子數量多出大約 22%。幾年後，這些結果得到了進一步改進，最終證明相對誤差可以做得任意小，儘管為此目的所需的 polynomial-time 演算法缺乏 Johnson 分析的首次適應遞減演算法的簡單性。

FIGURE 7. A Packing Created by the First-Fit Decreasing Algorithm 圖 7. 首次適應遞減演算法創建的裝箱方案

(示意圖顯示了大小不一的物品被裝入容量相等的箱子中，根據首次適應遞減演算法的結果。)

關於多項式時間近似演算法的研究揭示了 NP 完備組合最佳化問題之間的有趣區別。對於某些問題，相對誤差可以做得任意小；對於其他問題，可以降到一定水平，但似乎無法再進一步；還有一些問題則抵制了尋找具有有界相對誤差演算法的所有嘗試；最後，對於某些問題，如果存在一個具有有界相對誤差的多項式時間近似演算法，則意味著 P = NP。

在我擔任行政職位後的休假年期間，我開始反思組合最佳化領域理論與實踐之間的差距。從理論上看，情況令人沮喪。幾乎所有想解決的問題都是 NP 完備的，而且在大多數情況下，多項式時間近似演算法無法提供在實踐中有用的性能保證。然而，許多演算法在實踐中似乎運作得非常好，即使它們缺乏理論基礎。例如，Lin 和 Kernighan 為旅行銷售員問題開發了一個非常成功的局部改進策略。他們的演算法只是從一條隨機路線開始，並通過增加和刪除一些連結不斷改進它，直到最終創建了一條無法通過此類局部變化改進的路線。在人為構造的實例上，他們的演算法表現災難性，但在實際應用中，可以依賴它提供接近最優的解決方案。單純形法也存在類似的情況，這是所有計算方法中最重要的之一：儘管某些人為構造的例子會導致它運行指數級步數，但它可靠地解決了應用中出現的大型線性規劃問題。

這種不精確或經驗法則演算法的成功似乎是一個需要解釋的經驗現象。而且進一步看來，解釋這種現象將不可避免地需要脫離傳統的複雜性理論範式，傳統範式根據演算法在可能呈現給它的最壞輸入上的性能來評估演算法。傳統的最壞情況分析 (worst-case analysis)——複雜性理論的主流——對應於這樣一個場景：要解決的問題實例由一個無限聰明的對手構造，該對手知道演算法的結構並選擇會最大程度地讓其難堪的輸入。這種場景導致結論認為單純形法和 Lin-Kernighan 演算法是無可救藥的有缺陷。我開始追求另一種方法，在這種方法中，假定輸入來自一個簡單地從某種合理的機率分佈中抽取其實例的用戶，既不試圖阻止也不試圖幫助演算法。

1975 年，我決定硬著頭皮，致力於組合演算法的機率分析 (probabilistic analysis) 研究。我必須說，這個決定需要一些勇氣，因為這條研究路線有其批評者，他們正確地指出，無法知道將呈現給演算法的輸入是什麼，並且如果能夠獲得保證，最好的類型將是最壞情況保證。然而，我覺得對於 NP 完備問題，我們無法獲得我們想要的最壞情況保證，並且機率方法是理解啟發式組合演算法在實踐中為何運作如此良好的最佳方法，或許是唯一方法。

機率分析從假設問題實例是從指定機率分佈中抽取開始。例如，對於旅行銷售員問題，一個可能的假設是 n 個城市的位置是從單位正方形上的均勻分佈中獨立抽取的。在這種假設下，我們可以研究最優路線長度的機率分佈，或者特定演算法產生的路線長度的機率分佈。理想情況下，目標是證明某些簡單演算法以高機率產生最優或接近最優的解決方案。當然，這種結果只有在假定的問題實例機率分佈與現實生活中出現的實例總體有一些相似之處時，或者機率分析足夠穩健以適用於廣泛的機率分佈時才有意義。

機率論中最引人注目的現象之一是大數定律 (laws of large numbers)，它告訴我們大量隨機事件的累積效應具有高度可預測性，即使個別事件的結果高度不可預測。例如，我們可以自信地預測，在多次公平硬幣拋擲中，大約一半的結果是正面。機率分析揭示了當輸入數據來自簡單機率分佈時，同樣的現象支配著許多組合最佳化演算法的行為：以非常高的機率，演算法的執行以高度可預測的方式演變，並且產生的解決方案接近最優。例如，Beardwood, Halton, 和 Hammersley 在 1960 年的一篇論文顯示，如果在單位正方形上獨立抽取 n 個城市的旅行銷售員問題，那麼當 n 非常大時，最優路線的長度幾乎肯定會非常接近某個絕對常數乘以城市數量的平方根。受他們的結果啟發，我證明了，當城市數量極大時，一個簡單的分治演算法 (divide-and-conquer algorithm) 幾乎肯定會產生一條長度非常接近最優路線長度的路線（見圖 8）。

FIGURE 8. A Divide-and-Conquer Algorithm for the Traveling Salesman Problem in the Plane 圖 8. 平面旅行銷售員問題的分治演算法

(示意圖顯示了將包含城市的區域分割成較小的矩形，在每個矩形內計算路線，然後將這些路線合併。)

該演算法首先將城市所在的區域分割成矩形，每個矩形包含少量城市。然後，它在每個矩形內的城市中構建一條最優路線。所有這些小路線的聯合與總體旅行銷售員路線非常相似，但由於對位於矩形邊界上的城市的額外拜訪而有所不同。最後，演算法執行一種局部手術，以消除這些冗餘拜訪並產生一條路線。

還有許多其他例子可以引用，其中簡單的近似演算法幾乎肯定能為 NP 完備最佳化問題的隨機大型實例提供接近最優的解決方案。例如，我的學生 Sally Floyd 在 Bentley, Johnson, Leighton, McGeoch, 和 McGeoch 關於裝箱問題的早期工作基礎上，最近證明了，如果待打包的物品獨立地從區間 (0, 1/2) 的均勻分佈中抽取，那麼無論物品數量有多少，首次適應遞減演算法幾乎肯定會產生一個浪費空間少於 10 個箱子容量的裝箱方案。

機率分析最顯著的應用之一是對線性規劃問題。從幾何上看，這個問題相當於找到多面體中離某個外部超平面最近的頂點。從代數上看，它等同於在線性不等式約束下最小化一個線性函數。線性函數衡量到超平面的距離，而線性不等式約束對應於限定多面體的超平面。

用於線性規劃問題的單純形法是一種爬山法 (hill-climbing method)。它重複地從一個頂點滑到相鄰的頂點，始終靠近外部超平面。當它到達一個比任何相鄰頂點都更接近該超平面的頂點時，演算法終止；這樣的頂點被保證是最優解。在最壞情況下，單純形法所需的迭代次數隨描述多面體所需的線性不等式數量呈指數增長，但在實踐中，迭代次數很少超過線性不等式數量的三或四倍。

西德的 Karl-Heinz Borgwardt 和 Berkeley 的 Steve Smale 是第一批使用機率分析來解釋單純形法及其變體不合理成功的研究人員。他們的分析依賴於某些多維積分的計算。由於我在數學分析方面的背景有限，我發現他們的方法難以理解。幸運的是，我在 Berkeley 的一位同事 Ilan Adler 提出了一種有望導致幾乎無需計算的機率分析方法；人們可以利用某些對稱性原理進行所需的平均，並神奇地得出答案。

沿著這條研究路線，Adler, Ron Shamir 和我在 1983 年證明了，在相當廣泛的機率假設下，某個版本的單純形法執行所需的預期迭代次數僅隨線性不等式數量的平方增長。Michael Todd 以及 Adler 和 Nimrod Megiddo 也通過多維積分得到了相同的結果。我相信這些結果極大地促進了我們對單純形法表現如此出色的理解。

組合最佳化演算法的機率分析是我過去十年研究的一個主要主題。1975 年，當我第一次致力於這個研究方向時，這類分析的例子非常少。現在，這個主題有數百篇論文，所有經典的組合最佳化問題都已經進行了機率分析。這些結果為我們理解這些問題在實踐中可以在多大程度上被馴服提供了相當大的幫助。然而，我認為這項嘗試只取得了部分成功。由於我們技術的局限性，我們仍然在使用最簡單的機率模型，即使如此，許多最有趣和最成功的演算法仍然超出了我們分析的範圍。總而言之，實用組合最佳化演算法的設計既是一門藝術，也是一門科學。

隨機演算法 (Randomized Algorithms)

從最早的計算機時代起，就時不時有人提出在執行過程中拋硬幣的演算法，但對這種隨機演算法 (randomized algorithms) 的系統研究直到 1976 年左右才開始。對這個主題的興趣是由兩個出奇高效的用於測試數字 n 是否為素數的隨機演算法引發的；其中一個演算法由 Solovay 和 Volker Strassen 提出，另一個由 Rabin 提出。Rabin 後來的一篇論文提供了更多例子和系統研究隨機演算法的動機，我的同事 Blum 指導的 John Gill 的博士論文為隨機演算法的一般理論奠定了基礎。

為了理解拋硬幣的優勢，讓我們再次回到與最壞情況分析相關的場景，在這種場景下，一個全知的對手選擇會最嚴重地考驗給定演算法的實例。隨機化使得演算法的行為即使在實例固定時也變得不可預測，因此對手選擇可能導致麻煩的實例變得困難，甚至不可能。這與橄欖球有一個有用的類比，其中演算法對應進攻方，對手對應防守方。確定性演算法就像一個在戰術選擇上完全可預測的球隊，讓對方球隊能夠疊加防守。正如任何四分衛所知，戰術選擇上的一點多樣化對於保持防守方的防線是至關重要的。

作為拋硬幣優勢的一個具體例子，我介紹一個我和 Rabin 在 1980 年發明的一個簡單的隨機模式匹配演算法 (randomized pattern-matching algorithm)。模式匹配問題 (pattern-matching problem) 是文本處理中的一個基本問題。給定一個稱為模式 (pattern) 的 n 位元字符串，和一個長得多的稱為文本 (text) 的位元字符串，問題是判斷模式是否在文本中作為連續區塊出現（見圖 9）。

FIGURE 9. A Pattern-Matching Problem 圖 9. 一個模式匹配問題

(示意圖顯示了一個較短的位元串「模式」和一個較長的位元串「文本」，並標示出模式在文本中出現的位置。)

解決這個問題的暴力方法是直接將模式與文本中的每一個 n 位元區塊進行比較。在最壞情況下，這種方法的執行時間與模式長度和文本長度的乘積成正比。在許多文本處理應用中，除非模式非常短，否則這種方法是無法接受的慢。

我們的方法通過一個簡單的雜湊 (hashing) 技巧繞過了這個困難。我們定義一個「指紋函數」 (fingerprinting function)，它將每個 n 位元字符串與一個短得多的稱為其指紋 (fingerprint) 的字符串相關聯。指紋函數的選擇使得可以快速地遍歷文本，計算每個 n 位元長區塊的指紋。然後，我們不再將模式與文本的每個這樣的區塊進行比較，而是將模式的指紋與每個這樣的區塊的指紋進行比較。如果模式的指紋與每個區塊的指紋都不同，那麼我們就知道模式沒有作為區塊出現在文本中。

比較短指紋而不是長字符串的方法極大地減少了運行時間，但這會導致誤匹配 (false matches) 的可能性，誤匹配發生在文本的某個區塊與模式具有相同的指紋，儘管模式和文本區塊實際上是不相等的。誤匹配是一個嚴重的問題；事實上，對於任何特定的指紋函數選擇，對手都可以構造一個模式和文本的例子，使得在文本的每個位置都發生誤匹配。因此，需要某種備用方法來防禦誤匹配，而指紋方法的優勢似乎就喪失了。

幸運的是，通過隨機化 (randomization) 可以恢復指紋的優勢。隨機方法不再使用單一的指紋函數，而是可以使用一系列龐大的易於計算的不同指紋函數。每當一個問題實例（包含模式和文本）呈現時，演算法從這個龐大的族中隨機選擇一個指紋函數，並使用該函數來測試模式和文本之間的匹配。因為指紋函數不是預先知道的，所以對手不可能構造一個可能導致誤匹配的問題實例；可以證明，無論模式和文本如何選擇，發生誤匹配的機率都非常小。例如，如果模式長 250 位元，文本長 4000 位元，可以使用易於計算的 32 位元指紋，仍然可以保證在每個可能的實例中，誤匹配的機率小於千分之一。在許多文本處理應用中，這種機率保證足以消除備用程序的需要，從而重新獲得了指紋方法的優勢。

隨機演算法和演算法的機率分析是兩種與確定性演算法的最壞情況分析不同的方法。在前一種情況下，隨機性被注入到演算法自身的行為中；在後一種情況下，假設隨機性存在於問題實例的選擇中。基於隨機演算法的方法顯然是更吸引人的，因為它避免了對演算法使用環境的假設。然而，隨機演算法尚未證明在對抗 NP 完備問題特有的組合爆炸方面有效，因此這兩種方法看來將繼續發揮各自的作用。

結論 (Conclusion)

這就來到了我的故事的結尾，我想用一些簡短的話來總結今天在理論計算機科學領域工作的感受。每當我參加年度 ACM Theory of Computing Symposium，或者參加每月一次的 Bay Area Theory Seminar，或者去 Berkeley 校園後山上的 Mathematical Sciences Research Institute，那裡正在進行為期一年的計算複雜性專案時，我都被這個領域正在進行的工作水平所震撼。我很自豪能與一個正在進行如此多傑出研究的領域相關聯，並且很高興我能夠時不時地幫助極有天賦的年輕研究人員在這個領域找到方向。感謝您給予我在這個場合代表我的領域的機會。

CR 分類及主題描述詞：A.O [通用文獻]: 傳記~自傳；F. 0 [計算理論]: 總論；F.1.1 [抽象設備計算]: 計算模型--可計算性理論；F.1.2 [抽象設備計算]: 計算模式--並行計算、機率計算；F.1.3 [抽象設備計算]: 複雜性類別--歸約性和完備性、複雜性類別之間的關係；F.2.0 [演算法與問題複雜性分析]: 總論；G.2.1 [離散數學]: 組合學；G.2.2 [離散數學]: 圖論；K.2 [計算史]: 人物 通用術語：性能、理論 額外關鍵詞和短語：Richard Karp, Turing Award 作者現地址：Richard Karp, 571 Evans Hall, University of California, Berkeley, CA 94720. 允許在不收費的情況下複製本材料的全部或部分，條件是複製件不得用於直接商業目的，並須註明 ACM 版權聲明以及出版物標題和日期，並註明複製是經 Association for Computing Machinery 許可。如欲以其他方式複製或再版，須繳納費用並/或獲得特定許可。