# 理查德·卡普：演算法與計算複雜性 > 圖靈獎得主回顧演算法研究生涯，談 NP 完全性、隨機化演算法與計算複雜性理論的意義。 - 原標題：#111 – Richard Karp: Algorithms and Computational Complexity - 期數：第 111 期 - 釋出日期：2020-07-26 - 嘉賓 / 主題：理查德·卡普：演算法與複雜性 - 網頁版：https://lex.qiaomu.ai/tw/ep/richard-karp/ - 官方頁面：https://lexfridman.com/richard-karp/ - 精讀字數：約 20117 字（閱讀約 45 分鐘） > 本文為 lex.qiaomu.ai 基於原始訪談的 AI 改寫中文精讀，非官方翻譯；引用請註明出處並連結網頁版。 1955 年，一個哈佛博士生加入了 Howard Aiken（霍華德·艾肯）的計算實驗室。實驗室裡有一臺叫 Mark IV 的機器，佔滿整個房間，人可以走進去，兩側是一排排繼電器。 機器經常出故障，原因有時候是蟲子真的飛進去，落在了開關上。英文裡 bug 這個詞後來變成了“程式錯誤”，但在那個年代，它是字面意義上的蟲子。 這個博士生叫理查德·卡普（Richard Karp）。三十年後他拿了圖靈獎，理由是“對演算法理論的研究”，其中包括埃德蒙茲-卡普演算法、霍普克拉夫特-卡普演算法，以及一篇 1971 年的論文。那篇論文裡，他證明了 21 個看起來毫不相干的組合問題，其實是同一個問題的不同馬甲。 這場訪談裡，卡普把這七十年的思考壓縮成了一次聊天。從 13 歲被一個幾何證明震住，到懷疑計算機永遠追不上六個月大的嬰兒。 ## 一個證明，能把一個孩子釘在原地 卡普 13 歲第一次接觸平面幾何，被證明的力量和形式之美震住了。 他講了邁克爾·拉賓（Michael Rabin）的一個故事。拉賓小時候因為調皮被趕出教室，在走廊裡晃盪，碰到兩個高年級學生在研究一個問題：兩個不相交的圓，它們之間的最短距離是多少。 拉賓想了一會兒說：連心線。把兩個圓心連起來，夾在兩圓之間的那一段就是最短的。因為任何連線兩圓的線段，向兩邊各延長一個半徑，就得到一條連線兩圓心的三段折線，它不可能比直線更短。 卡普說，他聽完這個證明，和拉賓一樣覺得這就是優雅。純推理，能得出一個無可爭辯的結論。 > 你可以用純推理確立一個幾何事實，而且無可爭辯。（理查德·卡普） 三角形內角和 180 度也是這樣。過一個頂點作對邊的平行線，利用內錯角相等，三個角拼成一個平角。卡普說這件事的驚人之處不在難，恰恰在它太容易了。容易，卻又如此有說服力。 他還說了一句挺誠實的話：自己的三維視覺很差，想象不出三維曲面和超平面。所以後來做線性規劃，他靠的是代數性質，幾何直覺幫不上忙。“在腦子裡看到一個多面體的最高點”這件事，對他而言是動機，還談不上工具。 ## 演算法在腦子裡長什麼樣 Lex 問他，設計演算法的時候腦子裡在發生什麼。 卡普的描述很樸素：演算法通常是一個內層迴圈的重複，所以他能“看到”當前解到目標解的距離在迭代中不斷縮小，直到最後落到精確解上。每一步都要保證在靠近，還要保證一定會收斂。 他拿旅行商問題舉例。有一個目標函式需要最小化，看著它一步步逼近最優值，這件事本身就很迷人。 這裡有一處區分值得停下來。設計演算法包含兩件事：直覺上猜到解長什麼樣，以及嚴格證明它一定會收斂、一定跑在某個複雜度內。哪一部分更難，魔法發生在哪裡？ 卡普的回答是：魔法就在於那個差值單調下降，你能眼看著各種指標一路改善，直到撞上最優解。 他接著提到高德納（Don Knuth）的一個說法：有一類人，能從審視計算過程的結構中獲得巨大的審美愉悅。高德納管這種人叫 geek。 卡普記得自己意識到“我就是這種人”的那個瞬間，是有人給他看匈牙利演算法解分配問題的時候。 ## 把一行數字減掉一個常數，最優解不變 分配問題：n 個男孩，n 個女孩，給定每個男孩和每個女孩配對的成本，求一種一一對應，把總成本壓到最低。 關鍵觀察只有一句話：**從矩陣的任意一行或任意一列減去同一個常數，最優排列不變。**因為某一行的所有元素都減了同樣的量，每個完整解的代價都減了同樣的量，比較關係沒變。 於是演算法就變成了：從非負矩陣出發，不斷地從行或列減去常數，始終保持所有元素非負，直到矩陣裡出現一個全零的完整排列。那個排列就是最優解。 實際做的時候要稍微繞一點。只減不加會把某些零變成負數，所以每一步是從一些行和列減去常數，再給另一些行和列加回去，讓已有的零保持不變。整體效果是總成本下降。 怎麼找這些行列？靠計算矩陣裡元素之間的一種最短路。聽起來繞，做起來是多項式時間的。 卡普說，如果他有動手能力，大概會喜歡做木工，把一塊木頭削成漂亮、有序的東西。迭代演算法那種有條不紊的性質，給他的是同一種快感。 這種審美不是後天培養的。他小時候靠心算四位數乘法自娛自樂，還靠從 1 開始不斷翻倍、直到記不住為止來催眠。在波士頓郊外的海灘度假村打暑期工，他的崗位是招攬顧客，對著麥克風喊“來吧來吧，五分錢玩一局”。同事是一群對學術毫無興趣的小混混，他靠心算四位數乘法把他們鎮住了。 ## 1971 年，21 個問題被綁上了同一條船 1971 年，斯蒂芬·庫克（Stephen Cook）發表了一篇論文，證明了一件事：**命題邏輯的可滿足性問題（SAT），和 NP 類裡的任何問題一樣難。** SAT 的表述簡單到可以在中學課堂上講。給你一堆由“與、或、非”構成的邏輯表示式，問是否存在一組變數賦值，讓整個表示式為真。 比如把 (A 或 B)、(A 或非 B)、(非 A 或 B)、(非 A 或非 B) 這四個子句全部“與”起來，你會發現無論 A 和 B 怎麼取值，總有一個子句是假的。這個公式不可滿足。 庫克證明的是：NP 裡的每一個問題，都能重寫成 SAT 的一個例項。 他用的工具是圖靈機。圖靈機極簡：一條紙帶，一個讀寫頭，一張有限的狀態轉移表。任何現實計算機上的演算法，都能翻譯成圖靈機上的等價程式。反過來，任何非確定性多項式時間的演算法，都能描述成一串“讀到某個符號、處於某個狀態、寫下新符號、移動到新狀態”的指令，而這串指令本身可以用邏輯公式寫出來。 卡普看到這篇論文時意識到：**SAT 是一個通用的組合問題。**所有解容易驗證的問題，都能翻譯成它。 > 看到庫克的證明，你會意識到 SAT 是所有 NP 問題的通用形式。而我憑之前解題的經驗知道，還有很多別的問題也帶著這種通用結構。（理查德·卡普） 於是他開始反方向找歸約：從 SAT 出發，能不能翻譯到別的問題上？ 第一個是整數規劃。跟線性規劃長得一樣，一組線性不等式，但變數必須是整數，甚至是 0 或 1。這個額外約束讓問題難得多。把 SAT 寫成整數規劃並不難：每個變數一個 0/1 變數，每個子句一條不等式。 第二個是團問題。圖裡有沒有一個大小為 k 的完全子圖，其中任意兩個頂點都相鄰。 這個歸約值得細看，因為它展示了這類翻譯是怎麼工作的。 把 SAT 公式寫成若干子句的合取，每個子句是一串變數或變數否定的析取。要滿足整個公式，每個子句裡至少要挑一個“真”的項，而且不能同時挑中同一個變數的正版本和負版本。 現在造一張圖：頂點是每個子句裡的每個項，也就是每一次變數出現。邊有兩類。第一類，同一個子句內的任意兩個頂點之間連邊，因為你只能從這個子句裡挑一個。第二類，如果兩個頂點是同一個變數的正負兩次出現，也連邊，因為你不能讓它既真又假。 那麼“挑一組互不相鄰的頂點，每個子句恰好挑一個”，對應的就是獨立集問題。而獨立集的大小等於子句數，就等價於原公式可滿足。 Lex 在訪談裡說他很難相信這件事是真的：一張圖和一條邏輯公式，居然能這樣對應起來。 > 我也很難相信。但它們就是有同樣的表達力。你可以把其中任何一個翻譯成另一個的語言。（理查德·卡普） 這裡有個細微但重要的點。表達力相同，不等於計算複雜度相同。兩個問題可以互相翻譯，但翻譯本身可能帶來規模爆炸，所以它們的難度未必一樣。卡普說得很清楚：它們等價的地方在於“誰能表達誰”，不在於“誰算得快”。 能夠確定的是：**這些問題要麼全都能在多項式時間內求解，要麼全都不能。** 1971 年那篇論文裡，卡普挑了 21 個基本的組合問題，覆蓋打包、覆蓋、匹配這些常見型別，證明它們全都和 SAT 等價。這等於把戰書扔在了地上：這樣的問題肯定還有一大堆。 ## NP 完全和 NP 難，差別在一個技術細節 卡普說這倆的區別是個“小小的技術性問題”，但值得講清楚。 決策問題的答案是是或否。比如“圖裡有沒有大小為 15 的團”。最佳化問題的答案是數值，比如“最大的團有多大”。 兩邊的難度是對應的。決策版本里最難的那批叫 NP 完全，最佳化版本里對應的最難的那批叫 NP 難。核心的等價鏈條一樣，只是問題的表述形式不同。 那麼，如果 P 等於 NP，證明會長什麼樣？ 卡普的回答很乾脆：**它會用到我們現在完全沒有的概念。**不管結論是等還是不等，證明都會來自盒子外面。 如果真的證明了 P 不等於 NP，世界的反應會是：對於絕大多數實際出現的組合問題，既然它們是 NP 完全的，就不存在高效演算法。但還有一點餘地，因為 NP 完全只說明“不能對所有例項都快”，不說明“不能對大多數例項快”。所以注意力會轉向啟發式和近似演算法，帶著更多寬容，接受“最優解拿不到，好解也行”。 如果證明了 P 等於 NP，衝擊是另一個量級。所有解容易驗證的問題，都能在多項式時間內求解。那意味著很多今天靠密碼學保護的東西會瞬間失去屏障。 ## 穩定匹配：主動出擊的人佔便宜 Lex 請卡普挑一個他覺得最美的組合演算法。 卡普選的是穩定匹配，也叫穩定婚姻問題。 n 個男孩，n 個女孩。每個男孩對女孩有一個偏好排序，每個女孩對男孩也有一個。一個匹配是“穩定”的，意思是：不存在兩對情侶，其中男孩更喜歡第二對的女孩，女孩也更喜歡第一對的男孩，於是這兩個人想私奔，把原來的伴侶丟下。 1962 年，大衛·蓋爾（David Gale）和勞埃德·沙普利（Lloyd Shapley）證明了兩件事：**任何一組偏好下，穩定匹配都存在，而且可以用一個極簡的演算法算出來。** 演算法是這樣：每個男孩按自己的偏好列表，依次向女孩求婚。女孩收到求婚先暫時接受，但保留換人的權利。如果後來收到更好的，就把原來的甩掉。男孩被拒之後不回頭，繼續往下一位求婚。女孩的處境只會越來越好，因為她的物件只會向上替換。男孩的處境只會越來越差，因為他只能往下走。 這個過程一定會結束，結束時所有人都匹配上了，而且沒有一對想私奔。 更妙的是：**主動求婚的一方拿到的是他能拿到的最好結果。**在每個男孩所有可能處於的穩定匹配中，這個演算法給出的那個，對他而言是最好的。反過來說，女孩拿到的是最差的。 > 這裡有個給男孩的教訓：你應該主動出擊，去求婚。（理查德·卡普） 這套東西在現實裡真的用。美國的住院醫師匹配系統就是這個思路，醫院和醫學生各自排偏好，跑一個穩定匹配。只不過現實一加約束就崩：如果一對夫妻想被分到同一個城市，穩定匹配立刻變成 NP 難。 卡普還提了一句讓人唏噓的事。蓋爾在諾貝爾獎頒出之前去世了，沒能分享這份榮譽。2012 年，沙普利和阿爾文·羅思（Alvin Roth）因為穩定匹配理論與市場設計拿了諾貝爾經濟學獎。 ## 加一點隨機，笨辦法就變聰明 拉賓-卡普演算法是卡普最得意的作品之一，因為它展示了隨機化的力量。 問題很基礎：在一個很長的文字里，找一個很短的詞出現在哪。 傳統做法是組合式的：逐位比對，用失敗函式之類的東西跳過不可能的位置。拉賓-卡普演算法走的是完全不同的路。 把每個詞看成一個數。字母是數字，字母表的大小是進位制。然後隨機挑一個大素數，把詞對應的數對素數取餘，得到一個“指紋”。 接著在長文字上滑動一個長度等於目標詞大小的視窗，計算每個視窗內容的指紋。這裡有個巧妙的性質：視窗往右滑一格，指紋的更新只需要幾次算術運算，不用重算整個視窗。 最後，把每個視窗的指紋和目標詞的指紋比對。相同就大機率是真的匹配，因為隨機素數保證了碰撞機率很低。萬一撞上了，回到原文驗證一下就行。 這個演算法同時拿到了兩個好處：計算量小，因為滑動更新很便宜；錯誤率低，因為隨機選的素數讓不同字串撞指紋的機率極小。代價是機率性的正確性，但這個機率可以被壓到任意小。 卡普用幾個例子解釋隨機化為什麼這麼好用。 第一個是選舉。理論上，從全國選民裡隨機抽幾千人，最受歡迎的那個候選人幾乎必然就是全國計票的結果。現實裡當然不行，因為每個選民都想讓自己的票被算進去，而且真正的隨機抽樣做不到，還可能碰上平票。但把人類社會的這些麻煩去掉，數學上它就是成立的。 第二個是素性測試。費馬小定理說，如果 n 是素數，那麼對 0 到 n-1 之間任何 a，a 的 n-1 次方模 n 都等於 a。反過來說，如果某個 a 讓這個等式不成立，n 就肯定不是素數。隨機挑幾個 a 試一下，如果全過，n 大機率是素數。實際的 Miller-Rabin 測試要更精細一些，因為存在偽素數，但思路就是這個。 第三個是卡普自己做過的工作：數一個邏輯公式集合有多少個解滿足其中至少一個。直接數會重複計數，因為一個解可能同時滿足好幾個公式。 他的辦法是把它看成一個 0/1 矩陣。行是公式，列是解，矩陣裡元素為 1 表示這個解滿足這個公式。目標是數有多少列至少含一個 1。 做法是按每行 1 的個數來抽樣行，1 多的行被抽中的機率大。抽到一行之後，沿著這一行裡的某個 1 往上走，只在這個 1 第一次出現的那一行計數。這樣每個列只會被算一次。最後得到一個統計上穩健的估計。 這套思路背後有一個更普適的原則：**如果一個現象在大多數情況下都出現，那麼隨機抽一個樣本，大機率能撞上它。** 代數恆等式測試也是這樣。兩個公式長得完全不一樣，你想知道它們是不是同一個東西。隨機取一組值代進去，如果結果不一致，分歧就暴露了。因為不相等的點太多，隨便挑一個就能撞上。 兩個公式不同，那它們在大多數取值點上都會不同。隨便挑一個點代進去，就能看到分歧。這條原則能用的地方遠比直覺多。 ## 最壞情況分析救不了所有人 上面聊的這些，都屬於最壞情況分析：不管輸入長什麼樣，演算法都必須在這個步數內完成。 卡普對這個框架的評價很清醒。**最壞情況分析證明一個演算法永遠好，那很好用。如果它證明一個演算法的解不總是好，你就得退一步，換個問題問：多經常能拿到好解？** Lex 接了一句：我們習慣了一旦最壞情況很差，就把這個演算法扔進垃圾桶。 卡普說，這很不幸。 他舉了 SAT 求解器。可滿足性問題是 NP 完全的，理論上不該有高效演算法。但現實中，工業級的 SAT 求解器能相當穩定地處理幾百萬個變數的例項，這些例項來自數位電路設計、程式正確性驗證等等。 結果是在那些領域裡幹活的人，習慣性地把可滿足性當成一個簡單問題。他們不知道、也不需要知道它在理論上的地位。 > 在那些應用領域，SAT 求解器工作得如此之好，以至於那裡的人傾向於認為可滿足性是個簡單問題。（理查德·卡普） 旅行商問題也一樣。這是個 NP 難問題，但用整數規劃加上一些數學技巧，人們在平面上分佈的城市裡，可以求出幾萬個城市的可證明最優解。規模大一點要跑幾個月機器，但一兩千個城市的例項，很快就能拿到最優解，而且是最優性的嚴格證明。 這就出了一個很有意思的缺口：理論上不該存在多項式演算法，實踐上卻跑得飛快。 ## 為什麼平均情況分析讓人失望 那能不能用平均情況分析，系統性地解釋“實踐上很好”這件事？ 卡普在這件事上有過親身經歷，而且他坦率地承認了失敗。 在他完成 NP 完全性的工作之後，他想給組合演算法找一點正面的光。既然最壞情況這麼悲觀，那就研究平均情況、高機率情況。但立刻冒出一個問題：**機率空間是什麼？什麼叫典型例項？** 這個問題非常難回答。於是他選了省事的做法：做極其簡化的假設。 比如生成一張隨機圖，做法是每次隨機選一條邊，一直加到邊數夠了為止。這套模型在數學界被研究得很透。 在這個模型裡，他和別人一起證明了一堆漂亮的結果。比如關於哈密頓迴路，一條經過每個頂點恰好一次的環。他們能證明：當邊數略微超過 n log n（n 是頂點數）時，這樣的環幾乎必然存在，而且存在一個高機率找到它的啟發式演算法。 整個圈子沿著這條線出了很多成果，是個很好玩的遊樂場，卡普自己也很享受。 > 但學界對這些結果的態度有點冷淡，因為我們做的假設太簡化了。過了一段時間，我得出結論：這對實際應用沒什麼咬合力。（理查德·卡普） 意思是，玩來玩去還是在玩具問題裡打轉。 Lex 追問：那能不能找出代表性的、真正有現實意義的例項集，就像機器學習那樣？機器學習最好的狀態，就是拿一個真實資料集，所有會議都在上面比效能。 卡普說，那邊沒有對應的東西。高德納曾經收集過各種來源的圖，建了一個“動物園”，可以研究演算法在不同型別圖上的表現。但問題在於，你怎麼定義一類你關心的圖？這個定義本身就是個非平凡的步驟。 > 沒有什麼是可以類比於監督學習裡的訓練集的。在組合問題這一塊，我們真的沒有那東西。（理查德·卡普） Lex 又問：現在資料集這麼龐大，理論電腦科學會不會長出一個經驗性的分支？比如拿 Facebook 的社交網路，分析它的子圖，得出的結論既在實踐上站得住，又在理論圈裡被認可。 卡普說，這個還沒實現。有一個叫實驗演算法學的領域，人們有時拿到一些例子家族，有時乾脆隨機生成，然後報告效能。但沒有任何有說服力的證據表明這些樣本代表什麼。 ## 小電路的假設，如果成立，整個層級會塌掉 在開放問題裡，卡普提到他和理查德·利普頓（Richard Lipton）1979 年的一篇論文。 問題是這樣：拿一個 NP 裡的問題，比如規模固定為 52 的旅行商問題。能不能造一個針對這個規模量身定製的、規模很小的布林電路？把圖的邊作為布林輸入喂進去，輸出“是否存在一條長度小於 L 的路徑”。 換句話說：這個問題有沒有多項式大小的電路？ 已知如果 P 等於 NP，那麼這些問題會有小電路。反方向呢？**一個問題可以每個規模都有小電路，但卻沒有統一的、對所有規模都適用的多項式時間演算法嗎？** 這裡的區別在於“統一”。小電路是一族，每個尺寸一張不同的電路圖，彼此之間可能毫無結構關係。多項式時間演算法是一段程式，處理所有尺寸。 要理解他們證明的結論，得先理解多項式層級。 層級的第一層是 P。第二層是 NP，也就是“存在一個 X，使得某性質成立”這種形式的命題。比如“存在一種著色，使得圖可以用這麼多顏色染好”。 再往上，是“對所有 X，存在 Y，使得……”。這是第三層。博弈論裡就有這種結構：對先手的所有策略，存在後手的一個策略，使得先手獲勝。 再往上，“存在 A，對所有 B，存在 C，使得……”。層數越高，問題越難。 卡普和利普頓證明的是：**如果 NP 有小電路，這個層級會塌縮到第二層。**加三個量詞、四個量詞、任意多量詞，都不會讓問題變得更難。 這個結論的用法是反證法。層級沒塌，說明 NP 大概沒有小電路。但卡普自己也承認，這隻能算證據，還算不上證明，而且這個證據的性質有點奇怪：它的邏輯是“因為這件事太荒誕了，所以它不會發生”。 他說了一句挺有意思的話：P 不等於 NP 這個命題本身就夠荒誕的，所以不管走哪條路，最後都得跟龍正面對上。 ## 神經網路就是電路，但沒人知道它在算什麼 Lex 把話題引向機器學習。 卡普認為這兩個世界差別很大。深度學習的成果基本是經驗性的，跟 SAT 求解器的情況類似：觀察到在這些實際出現的輸入上效果很好，就這樣。 他不否認成功。影象處理、機器人、自然語言處理、遊戲博弈，都有巨大突破。副作用是，在機器學習界混出名聲之後，想變成百萬富翁不難，一堆公司願意開出天價，因為它們相信只要有 AI，什麼問題都能解。 但侷限也明顯。 第一，卷積神經網路在訓練集之外的輸入上表現驚人地好，可我們沒有任何理論能解釋為什麼。 第二，訓練出來的網路極難理解，幾乎榨不出什麼洞察。它能在你的訓練集上工作，也能分辨一張照片是否來自另一個樣本，但我們不知道它到底在看什麼。哪些特徵在區分照片和物體，很難刻畫出來。 Lex 提了一個有意思的類比：你說的“為某個規模定製的小電路”，神經網路不就是小電路嗎？ 卡普說，某種意義上是的，但神經網路算不上程式。他隨即修正了一下：它當然是一個演算法，是一個可計算函式，給它輸入就能算出輸出。但它沒有對輸入做演算法式操作的那種結構。 > 如果要在影象裡識別什麼，你不知道影象的哪些特徵真正決定了電路在幹什麼。電路非常精細複雜，你期待的那些簡單特徵，比如物體的邊緣，並沒有從電路結構裡浮現出來。（理查德·卡普） Lex 反問：人看不清這層，電路自己卻清楚。 卡普說，對。就像人類大腦對自己怎麼工作也不清楚，但我們能互相解釋推理過程，這正是認知科學和心理學存在的理由。 Lex 順著說，也許“對人類可解釋”這件事被高估了。 卡普承認有這個可能，但也補了一句：至少視覺系統、聽覺系統，我們確實理解了一些原理。而更深的認知任務，我們確實沒有。 ## 基因編輯：把生物系統拉進演算法的世界 卡普做過生物資訊學的工作。Lex 問他，人類的智慧，全部編碼在 DNA 裡，這件事是否讓他驚歎。 卡普說驚歎，更驚歎的是我們開始學會編輯 DNA 了。 > 能取一段序列，在基因組裡找到它，然後對它做點什麼。這真的把生物系統拉進了演算法的世界。（理查德·卡普） 但他馬上提到倫理問題。要區分兩種情況：編輯一個個體，和編輯生殖細胞。後者意味著所有後代都會受影響。即便是編輯個體，也有大量的傲慢在裡面：你假定敲掉某個基因會帶來好處，可你不知道副作用是什麼。 他說基因編輯在農業和醫學上都有巨大潛力，但嚴重的倫理問題一定會擺到檯面上。 演算法在這一側能做的，是分析基因組資料。搞清楚哪些基因在細胞裡起作用、在什麼條件下起作用，哪些蛋白質影響彼此、哪些有物理相互作用。還能對蛋白質測序並修改它們。 這算不算電腦科學問題？卡普說，這是大資料統計問題，肯定算。生物資料集在膨脹，對祖先的追溯、對疾病傾向的評估、按基因組做個性化治療，全都在這條線上。 ## 為什麼普通人也會被數學吸引 Lex 問了一個傳播學的問題。YouTube 上有個頻道叫 Numberphile，專門講數學想法，是最受歡迎的科學頻道之一。觀眾即使聽不懂在講什麼，也會被吸引。這種吸引力來自哪裡？ 卡普的回答很實在。你能做到一些了不起的事：檢驗一個大數是不是素數，解一些傳教士與野人的小謎題。這是一種成就感，是解謎。 再往上一層，是推理本身的力量。你能以鐵一般的方式證明三角形內角和是 180 度。 > 這是對現實世界之混亂的一種逃離。在現實世界裡，什麼都證明不了。（理查德·卡普） 他還補了一句帶點自嘲的話：geek 的另一個特點，是未必具備情緒智力，所以他們能活在抽象世界裡，不必去掌握與人打交道的複雜性。 這句話放在整場訪談裡回看，其實埋了一根線。他後面講自己父親、講教書、講學生，講的都是他後來學會的那部分。 ## Mark IV、Univac，和母親的建議 回到 1955 年。 Mark IV 佔滿一整個房間，比他們錄訪談的那間辦公室大得多。人可以在裡面走動，兩側是成排的繼電器。機器有時會因為真正的蟲子落在開關上而故障。 卡普說他從沒用那臺機器做過任何實際用途的事。實驗室後來弄到了一臺早期商用計算機，Univac，2000 個字的儲存。 2000 個字。這意味著記憶體分配是一門藝術。從一個字取資料到另一個字，訪問時間取決於字的編號，所以怎麼安排儲存位置能取數快，需要動腦子。 Lex 問他，是不是被這種“物理地做數學的機器”吸引。 卡普說不是，他感興趣的是底層的演算法。 那當年能想象六十年後全世界有幾十億臺計算機嗎？ 不能。但實驗室裡有一種感覺：這是未來的浪潮。他母親起了作用，她告訴他，資料處理會變得非常重要，他應該進去。 > 我母親是個聰明的女人。（理查德·卡普） 他說，當時的感覺是這東西會改變世界，但完全沒想到個人計算。沒想到我們會把計算機裝進口袋裡到處走。 至於 AI，那時候不在他的雷達上。他讀過圖靈的論文，就是提出圖靈測試的那篇《計算機器與智慧》。但他認為圖靈測試不夠格，因為它太主觀，沒法用來校準一個演算法有多智慧。 ## 沒有程式能超過六個月大的嬰兒 Lex 把話題推到智慧本身：能不能造出在推理上和人一樣、在我們看來同樣智慧的演算法？ 卡普的回答是：開放問題。但他的傾向很清楚。 他認為已有的成果，絕大多數都執行在一套非常有限的規則裡，針對非常精確的單一任務。這跟人腦裡發生的事情差別很大。人要在變化的環境中運作，有情緒，有探索環境的身體，有直覺，有慾望。他在當前所謂 AI 的成就裡，看不到任何東西接近這種能力。 > 我不認為有任何計算機程式，在世界理解這件事上超過了一個六個月大的嬰兒。（理查德·卡普） 那如果堅持一個前提：大腦本質上就是一大堆互相連線的開關。原則上，只要搞清楚連線結構、刻畫清楚每個開關，就能在外面造一個模擬。 卡普承認這在原則上是存在的證明。但他說，**那不會是我們最終解決這個問題的方式，這條路走不通。**要去獲取那種級別的資訊，幾乎不可能。 Lex 追問意識。主觀體驗這件事，我們完全沒有頭緒。這樣一張開關網路，能造出“知道自己”這種東西嗎？ 卡普說，如果你想把“知道自己”嚴格定義出來，會遇到巨大困難。 他知道有很多人相信通用智慧可以實現，有些人甚至確信奇點會到來，機器會超越我們，然後不斷自我學習，把人類降為劣等物種。 > 我懷疑這永遠不會實現。（理查德·卡普） 理由只有一個：語音、機器人、自然語言處理、靈活的計算助手，這些成就沒有一個接近那個級別的認知。 Lex 丟擲了摩爾定律這個反駁：我們習慣線性思考，想象不出從 Mark I 到 iPhone X 的跨度。會不會指數增長再一次讓人大吃一驚？ 卡普的回答是：**任何常數因子的改進都改變不了局面。**按我們現在對認知需要什麼的理解，把開關速度提高一千倍、一百萬倍，在真正理解那張開關網路背後的組織原理之前，都沒有用。 ## 什麼是組合演算法 Lex 請卡普從最基礎講起。訪談到了這兒，氣氛最接近課堂。 組合演算法處理的是離散物件的系統。這些物件可以處於不同狀態，或者取一組離散值中的某個值，需要被安排或挑選，以最小化某個成本函式，或者證明某種組合構型存在。 圖是什麼？ 一組點，其中某些點對之間用線連起來，這些線叫邊。在不同應用裡，它表示離散物件之間的互聯關係：數位電路里開關之間的連線，人類社群裡的通訊模式，公路系統裡城市之間的道路。 邊可以是有向的，也可以是無向的。通訊網路裡，無向邊表示資訊雙向流動，有向邊表示單向。邊上還可以帶權，比如公路的距離。 然後是應用的列舉，卡普一口氣給了一串。 學校排課：頂點是課程，邊表示約束，某些課不能同時開，某些老師只在特定時段可用。 分配問題：每個男孩到每個女孩一條帶權邊，權是成本。 邏輯電路設計：要找一組閘電路，互相連線起來實現某個邏輯函式。比如“輸入裡至少 k 個為 1 時輸出是，否則輸出否”，需要多少個門才夠。 Lex 說他最喜歡網路流，因為太直觀了。管道和水，可以對映到通訊網路、交通流，視覺上和智力上都吸引人。 卡普解釋：邊表示通道，上面流著某種商品，可能是天然氣、水、資訊，也可能是產品從一個工序流到下一個工序。邊上有容量，表示流速上限。中心問題是，給定這樣一張網路，從源點到匯點的最大流速是多少。 ## 第一批證明最大流屬於多項式時間的人 這是卡普和傑克·埃德蒙茲（Jack Edmonds）合作的工作。 > 我想我們是第一批給出形式證明的人：網路最大流問題可以在多項式時間內求解。（理查德·卡普） Lex 說他第一次學到這個結論時非常驚訝。最大流居然有多項式演算法，一個漂亮又快的演算法。 多項式時間到底是什麼意思？ 卡普從輸入開始講。一個問題有一組輸入資料，比如一張圖，每個頂點、每條邊、每條邊的容量。演算法是一段程式，基本操作是加減乘除、比較大小。 目標是用最少的計算步數得到答案。這裡的“一步”就是一次這樣的操作。 如果所需步數，作為輸入規模（頂點數、邊數）的函式，只按某個固定冪次增長，就叫多項式時間。線性演算法是步數與規模成正比，平方演算法是步數與規模的平方成正比。 **理論家把“高效”定義成這個。**這個定義可以商榷：一個跑到輸入規模一萬次方的演算法，顯然談不上高效。實踐裡真正有意義的跳躍，往往是從 n² 降到 n log n 或者線性，因為網路規模可以到幾百萬，任何高於 n log n 的東西都太慢了。 那 NP 是什麼？ **NP 是那些可能很難求解，但拿到一個解之後可以在多項式時間內驗證的問題類。** 卡普用團問題舉例。一張圖裡有沒有大小為 k 的完全子圖，其中任意兩個頂點都相鄰？這個問題很難。但如果有人遞給你一組頂點，問這組是不是團，你只需要把組內所有頂點對之間的邊都檢查一遍，那是多項式時間。 找團很難，驗團很容易。這類問題就叫非確定性多項式時間，也就是 NP。 有一個顯然的包含關係：**P 裡的每個問題也在 NP 裡。**能精確求解，當然也能驗證解。反過來成不成立，就沒人知道了。 排課也是這樣。拿到一張排好的課表，你能快速驗證它滿足所有要求。這不意味著你能快速找到這樣一張課表。 直覺上，能驗證的類會比能求解的類大得多。這裡必須加一句“看起來”，因為沒人證明過。 ## 為什麼敢賭 P 不等於 NP Lex 讓卡普押上全部身家賭一把。 卡普賭 P 不等於 NP。理由很樸素：有些問題已經存在了幾個世紀，數學界密集研究了很久，特別是 P 與 NP 提出之後的這五十年，仍然沒有找到多項式時間演算法。 他舉的例子是因數分解，可以追溯到高斯。素數就是不能寫成兩個大於一的整數乘積的數。91 等於 7 乘 13，這好辦。但給你一個 20 位、30 位的數，你大概就束手無策了。反過來，一旦有人把因子給你，你驗證乘起來對不對是瞬間的事。 這裡有一層現實含義，卡普沒有明說但很明顯：**今天大量公鑰密碼系統的安全性，就架在“因數分解沒有高效演算法”這個信念上。**它算不上定理，只能算信念。 > 如果 P 不等於 NP，我們同時也就知道，幾乎所有標準的組合問題都不能在多項式時間內求解。（理查德·卡普） 這就是 1971 年那篇論文的分量。它把成百上千個看起來無關的問題綁成了一束：要麼全都能高效求解，要麼全都不行。攻破其中一個，整束就全破了。 而這一切的起點，是庫克證明的那件事：SAT 和 NP 裡的任何問題一樣難。 卡普在訪談裡對庫克的工作給了很高的評價。他說看庫克的證明，理解為什麼成立並不算太難，但含義令人震驚。**所有解容易驗證的問題，全都能重寫成同一個問題的形式。** ## 穩定匹配：主動出擊的人佔便宜 Lex 請卡普挑一個他心目中最美的組合演算法。 卡普選的是穩定匹配，也叫穩定婚姻問題。 n 個男孩，n 個女孩。每個男孩對女孩有一個偏好排序，每個女孩對男孩也有一個。一個匹配是“穩定”的，意思是：不存在兩對情侶，其中男孩更喜歡第二對的女孩，女孩也更喜歡第一對的男孩，於是這兩個人想私奔，把原來的伴侶丟下。 1962 年，大衛·蓋爾（David Gale）和勞埃德·沙普利（Lloyd Shapley）證明了兩件事：**任何一組偏好下，穩定匹配都存在，而且可以用一個極簡的演算法算出來。** 演算法是這樣：每個男孩按自己的偏好列表，依次向女孩求婚。女孩收到求婚先暫時接受，但保留換人的權利。如果後來收到更好的，就把原來的甩掉。男孩被拒之後不回頭，繼續往下一位求婚。女孩的處境只會越來越好，因為她的物件只會向上替換。男孩的處境只會越來越差，因為他只能往下走。 這個過程一定會結束，結束時所有人都匹配上了，而且沒有一對想私奔。 更妙的是：**主動求婚的一方拿到的是他能拿到的最好結果。**在每個男孩所有可能處於的穩定匹配中，這個演算法給出的那個，對他而言是最好的。反過來說，女孩拿到的是最差的。 > 這裡有個給男孩的教訓：你應該主動出擊，去求婚。（理查德·卡普） 這套東西在現實裡真的用。美國的住院醫師匹配系統就是這個思路，醫院和醫學生各自排偏好，跑一個穩定匹配。現實一加約束就崩：如果一對夫妻想被分到同一個城市，穩定匹配立刻變成 NP 難。 卡普還提了一句讓人唏噓的事。蓋爾在諾貝爾獎頒出之前去世了，沒能分享這份榮譽。2012 年，沙普利和阿爾文·羅思（Alvin Roth）因為穩定匹配理論與市場設計拿了諾貝爾經濟學獎。 ## 加一點隨機，笨辦法就變聰明 拉賓-卡普演算法是卡普最得意的作品之一，因為它展示了隨機化的力量。 問題很基礎：在一個很長的文字里，找一個很短的詞出現在哪。 傳統做法是組合式的：逐位比對，用失敗函式之類的東西跳過不可能的位置。拉賓-卡普演算法走的是完全不同的路。 把每個詞看成一個數。字母是數字，字母表的大小是進位制。然後隨機挑一個大素數，把詞對應的數對素數取餘，得到一個“指紋”。 接著在長文字上滑動一個長度等於目標詞大小的視窗，計算每個視窗內容的指紋。這裡有個巧妙的性質：視窗往右滑一格，指紋的更新只需要幾次算術運算，不用重算整個視窗。 最後，把每個視窗的指紋和目標詞的指紋比對。相同就大機率是真的匹配，因為隨機素數保證了碰撞機率很低。萬一撞上了，回到原文驗證一下就行。 這個演算法同時拿到了兩個好處：計算量小，因為滑動更新很便宜；錯誤率低，因為隨機選的素數讓不同字串撞指紋的機率極小。代價是機率性的正確性，但這個機率可以被壓到任意小。 卡普用幾個例子解釋隨機化為什麼這麼好用。 第一個是選舉。理論上，從全國選民裡隨機抽幾千人，最受歡迎的那個候選人幾乎必然就是全國計票的結果。現實裡當然不行，因為每個選民都想讓自己的票被算進去，而且真正的隨機抽樣做不到，還可能碰上平票。把人類社會的這些麻煩去掉，數學上它就是成立的。 第二個是素性測試。費馬小定理說，如果 n 是素數，那麼對 0 到 n-1 之間任何 a，a 的 n-1 次方模 n 都等於 a。反過來說，如果某個 a 讓這個等式不成立，n 就肯定不是素數。隨機挑幾個 a 試一下，如果全過，n 大機率是素數。實際的 Miller-Rabin 測試要更精細一些，因為存在偽素數，但思路就是這個。 第三個是卡普自己做過的工作：數一個邏輯公式集合有多少個解滿足其中至少一個。直接數會重複計數，因為一個解可能同時滿足好幾個公式。 他的辦法是把它看成一個 0/1 矩陣。行是公式，列是解，矩陣裡元素為 1 表示這個解滿足這個公式。目標是數有多少列至少含一個 1。 做法是按每行 1 的個數來抽樣行，1 多的行被抽中的機率大。抽到一行之後，沿著這一行裡的某個 1 往上走，只在這個 1 第一次出現的那一行計數。這樣每個列只會被算一次。最後得到一個統計上穩健的估計。 這套思路背後有一個更普適的原則：**如果一個現象在大多數情況下都出現，那麼隨機抽一個樣本，大機率能撞上它。** 代數恆等式測試也是這樣。兩個公式長得完全不一樣，你想知道它們是不是同一個東西。隨機取一組值代進去，如果結果不一致，分歧就暴露了。因為不相等的點太多，隨便挑一個就能撞上。 兩個公式不同，那它們在大多數取值點上都會不同。隨便挑一個點代進去，就能看到分歧。這條原則能用的地方遠比直覺多。 ## 最壞情況分析救不了所有人 上面聊的這些，都屬於最壞情況分析：不管輸入長什麼樣，演算法都必須在這個步數內完成。 卡普對這個框架的評價很清醒。**最壞情況分析證明一個演算法永遠好，那很好用。如果它證明一個演算法的解不總是好，你就得退一步，換個問題問：多經常能拿到好解？** Lex 接了一句：我們習慣了一旦最壞情況很差，就把這個演算法扔進垃圾桶。 卡普說，這很不幸。 他舉了 SAT 求解器。可滿足性問題是 NP 完全的，理論上不該有高效演算法。但現實中，工業級的 SAT 求解器能相當穩定地處理幾百萬個變數的例項，這些例項來自數位電路設計、程式正確性驗證等等。 結果是在那些領域裡幹活的人，習慣性地把可滿足性當成一個簡單問題。他們不知道、也不需要知道它在理論上的地位。 > 在那些應用領域，SAT 求解器工作得如此之好，以至於那裡的人傾向於認為可滿足性是個簡單問題。（理查德·卡普） 旅行商問題也一樣。這是個 NP 難問題，但用整數規劃加上一些數學技巧，人們在平面上分佈的城市裡，可以求出幾萬個城市的可證明最優解。規模大一點要跑幾個月機器，但一兩千個城市的例項，很快就能拿到最優解，而且是最優性的嚴格證明。 這裡就出了一個很有意思的缺口：理論上不該存在多項式演算法，實踐上卻跑得飛快。 ## 為什麼平均情況分析讓人失望 那能不能用平均情況分析，系統性地解釋“實踐上很好”這件事？ 卡普在這件事上有過親身經歷，而且他坦率地承認了失敗。 在他完成 NP 完全性的工作之後，他想給組合演算法找一點正面的光。既然最壞情況這麼悲觀，那就研究平均情況、高機率情況。立刻冒出一個問題：**機率空間是什麼？什麼叫典型例項？** 這個問題非常難回答。於是他選了省事的做法：做極其簡化的假設。 比如生成一張隨機圖，做法是每次隨機選一條邊，一直加到邊數夠了為止。這套模型在數學界被研究得很透。 在這個模型裡，他和別人一起證明了一堆漂亮的結果。比如關於哈密頓迴路，一條經過每個頂點恰好一次的環。他們能證明：當邊數略微超過 n log n（n 是頂點數）時，這樣的環幾乎必然存在，而且存在一個高機率找到它的啟發式演算法。 整個圈子沿著這條線出了很多成果，是個很好玩的遊樂場，卡普自己也很享受。 > 但學界對這些結果的態度有點冷淡，因為我們做的假設太簡化了。過了一段時間，我得出結論：這對實際應用沒什麼咬合力。（理查德·卡普） 意思是，玩來玩去還是在玩具問題裡打轉。 Lex 追問：那能不能找出代表性的、真正有現實意義的例項集，就像機器學習那樣？機器學習最好的狀態，就是拿一個真實資料集，所有會議都在上面比效能。 卡普說，那邊沒有對應的東西。高德納曾經收集過各種來源的圖，建了一個“動物園”，可以研究演算法在不同型別圖上的表現。問題在於，你怎麼定義一類你關心的圖？這個定義本身就是個非平凡的步驟。 > 沒有什麼是可以類比於監督學習裡的訓練集的。在組合問題這一塊，我們真的沒有那東西。（理查德·卡普） Lex 又問：現在資料集這麼龐大，理論電腦科學會不會長出一個經驗性的分支？比如拿 Facebook 的社交網路，分析它的子圖，得出的結論既在實踐上站得住，又在理論圈裡被認可。 卡普說，這個還沒實現。有一個叫實驗演算法學的領域，人們有時拿到一些例子家族，有時乾脆隨機生成，然後報告效能。但沒有任何有說服力的證據表明這些樣本代表什麼。 ## 小電路的假設一旦成立，層級會整個塌掉 在開放問題裡，卡普提到他和理查德·利普頓（Richard Lipton）1979 年的一篇論文。 問題是這樣：拿一個 NP 裡的問題，比如規模固定為 52 的旅行商問題。能不能造一個針對這個規模量身定製的、規模很小的布林電路？把圖的邊作為布林輸入喂進去，輸出“是否存在一條長度小於 L 的路徑”。 換句話說：這個問題有沒有多項式大小的電路？ 已知如果 P 等於 NP，那麼這些問題會有小電路。反方向呢？**一個問題可以每個規模都有小電路，但卻沒有統一的、對所有規模都適用的多項式時間演算法嗎？** 區別在於“統一”。小電路是一族，每個尺寸一張不同的電路圖，彼此之間可能毫無結構關係。多項式時間演算法是一段程式，處理所有尺寸。 要理解他們證明的結論，得先理解多項式層級。 層級的第一層是 P。第二層是 NP，也就是“存在一個 X，使得某性質成立”這種形式的命題。比如“存在一種著色，使得圖可以用這麼多顏色染好”。 再往上，是“對所有 X，存在 Y，使得……”。這是第三層。博弈論裡就有這種結構：對先手的所有策略，存在後手的一個策略，使得先手獲勝。 再往上，“存在 A，對所有 B，存在 C，使得……”。層數越高，問題越難。 卡普和利普頓證明的是：**如果 NP 有小電路，這個層級會塌縮到第二層。**加三個量詞、四個量詞、任意多量詞，都不會讓問題變得更難。 這個結論的用法是反證法。層級沒塌，說明 NP 大概沒有小電路。卡普自己也承認，這隻能算證據，還算不上證明，而且這個證據的性質有點奇怪：它的邏輯是“因為這件事太荒誕了，所以它不會發生”。 他說了一句挺有意思的話：P 不等於 NP 這個命題本身就夠荒誕的，所以不管走哪條路，最後都得跟龍正面對上。 ## 神經網路就是電路，但沒人知道它在算什麼 Lex 把話題引向機器學習。 卡普認為這兩個世界差別很大。深度學習的成果基本是經驗性的，跟 SAT 求解器的情況類似：觀察到在這些實際出現的輸入上效果很好，就這樣。 他不否認成功。影象處理、機器人、自然語言處理、遊戲博弈，都有巨大突破。副作用是，在機器學習界混出名聲之後，想變成百萬富翁不難，一堆公司願意開出天價，因為它們相信只要有 AI，什麼問題都能解。 侷限也明顯。 第一，卷積神經網路在訓練集之外的輸入上表現驚人地好，可我們沒有任何理論能解釋為什麼。 第二，訓練出來的網路極難理解，幾乎榨不出什麼洞察。它能在你的訓練集上工作，也能分辨一張照片是否來自另一個樣本，但我們不知道它到底在看什麼。哪些特徵在區分照片和物體，很難刻畫出來。 Lex 提了一個有意思的類比：你說的“為某個規模定製的小電路”，神經網路不就是小電路嗎？ 卡普說，某種意義上是的，但神經網路算不上程式。他隨即修正了一下：它當然是一個演算法，是一個可計算函式，給它輸入就能算出輸出。但它沒有對輸入做演算法式操作的那種結構。 > 如果要在影象裡識別什麼，你不知道影象的哪些特徵真正決定了電路在幹什麼。電路非常精細複雜，你期待的那些簡單特徵，比如物體的邊緣，並沒有從電路結構裡浮現出來。（理查德·卡普） Lex 反問：人看不清這層，電路自己卻清楚。 卡普說，對。就像人類大腦對自己怎麼工作也不清楚，但我們能互相解釋推理過程，這正是認知科學和心理學存在的理由。 Lex 順著說，也許“對人類可解釋”這件事被高估了。 卡普承認有這個可能，但也補了一句：至少視覺系統、聽覺系統，我們確實理解了一些原理。更深的認知任務，我們確實沒有。 ## 基因編輯：把生物系統拉進演算法的世界 卡普做過生物資訊學的工作。Lex 問他，人類的智慧全部編碼在 DNA 裡，這件事是否讓他驚歎。 卡普說驚歎，更驚歎的是我們開始學會編輯 DNA 了。 > 能取一段序列，在基因組裡找到它，然後對它做點什麼。這真的把生物系統拉進了演算法的世界。（理查德·卡普） 但他馬上提到倫理問題。要區分兩種情況：編輯一個個體，和編輯生殖細胞。後者意味著所有後代都會受影響。即便是編輯個體，也有大量的傲慢在裡面：你假定敲掉某個基因會帶來好處，可你不知道副作用是什麼。 他說基因編輯在農業和醫學上都有巨大潛力，但嚴重的倫理問題一定會擺到檯面上。 演算法在這一側能做的，是分析基因組資料。搞清楚哪些基因在細胞裡起作用、在什麼條件下起作用，哪些蛋白質影響彼此、哪些有物理相互作用。還能對蛋白質測序並修改它們。 這算不算電腦科學問題？卡普說，這是大資料統計問題，肯定算。生物資料集在膨脹，對祖先的追溯、對疾病傾向的評估、按基因組做個性化治療，全都在這條線上。 ## 為什麼普通人也會被數學吸引 Lex 問了一個傳播學的問題。YouTube 上有個頻道叫 Numberphile，專門講數學想法，是最受歡迎的科學頻道之一。觀眾即使聽不懂在講什麼，也會被吸引。這種吸引力來自哪裡？ 卡普的回答很實在。你能做到一些了不起的事：檢驗一個大數是不是素數，解一些傳教士與野人的小謎題。這是成就感，是解謎。 再往上一層，是推理本身的力量。你能以鐵一般的方式證明三角形內角和是 180 度。 > 這是對現實世界之混亂的一種逃離。在現實世界裡，什麼都證明不了。（理查德·卡普） 他還補了一句帶點自嘲的話：geek 的另一個特點，是未必具備情緒智力，所以他們能活在抽象世界裡，不必去掌握與人打交道的複雜性。 這句話放在整場訪談裡回看，其實埋了一根線。他後面講自己父親、講教書、講學生，講的都是他後來學會的那部分。 ## Mark IV、Univac，和母親的建議 回到 1955 年。 Mark IV 佔滿一整個房間，比他們錄訪談的那間辦公室大得多。人可以在裡面走動，兩側是成排的繼電器。機器有時會因為真正的蟲子落在開關上而故障。 卡普說他從沒用那臺機器做過任何實際用途的事。實驗室後來弄到了一臺早期商用計算機，Univac，2000 個字的儲存。 2000 個字。這意味著記憶體分配是一門藝術。從一個字取資料到另一個字，訪問時間取決於字的編號，所以怎麼安排儲存位置能取數快，需要動腦子。 Lex 問他，是不是被這種“物理地做數學的機器”吸引。 卡普說不是，他感興趣的是底層的演算法。 那當年能想象六十年後全世界有幾十億臺計算機嗎？ 不能。但實驗室裡有一種感覺：這是未來的浪潮。他母親起了作用，她告訴他，資料處理會變得非常重要，他應該進去。 > 我母親是個聰明的女人。（理查德·卡普） 他說，當時的感覺是這東西會改變世界，但完全沒想到個人計算。沒想到我們會把計算機裝進口袋裡到處走。 至於 AI，那時候不在他的雷達上。他讀過圖靈的論文，就是提出圖靈測試的那篇《計算機器與智慧》。他認為圖靈測試不夠格，因為它太主觀，沒法用來校準一個演算法有多智慧。 ## 沒有程式能超過六個月大的嬰兒 Lex 把話題推到智慧本身：能不能造出在推理上和人一樣、在我們看來同樣智慧的演算法？ 卡普的回答是：開放問題。他的傾向很清楚。 已有的成果，絕大多數都執行在一套非常有限的規則裡，針對非常精確的單一任務。這跟人腦裡發生的事情差別很大。人要在變化的環境中運作，有情緒，有探索環境的身體，有直覺，有慾望。他在當前所謂 AI 的成就裡，看不到任何東西接近這種能力。 > 我不認為有任何計算機程式，在世界理解這件事上超過了一個六個月大的嬰兒。（理查德·卡普） 那如果堅持一個前提：大腦本質上就是一大堆互相連線的開關。原則上，只要搞清楚連線結構、刻畫清楚每個開關，就能在外面造一個模擬。 卡普承認這在原則上是存在的證明。但他說，**那不會是我們最終解決這個問題的方式，這條路走不通。**要去獲取那種級別的資訊，幾乎不可能。 Lex 追問意識。主觀體驗這件事，我們完全沒有頭緒。這樣一張開關網路，能造出“知道自己”這種東西嗎？ 卡普說，如果你想把“知道自己”嚴格定義出來，會遇到巨大困難。 他知道有很多人相信通用智慧可以實現，有些人甚至確信奇點會到來，機器會超越我們，然後不斷自我學習，把人類降為劣等物種。 > 我懷疑這永遠不會實現。（理查德·卡普） 理由只有一個：語音、機器人、自然語言處理、靈活的計算助手，這些成就沒有一個接近那個級別的認知。 Lex 丟擲了摩爾定律這個反駁：我們習慣線性思考，想象不出從 Mark I 到 iPhone X 的跨度。會不會指數增長再一次讓人大吃一驚？ 卡普的回答是：**任何常數因子的改進都改變不了局面。**按我們現在對認知需要什麼的理解，把開關速度提高一千倍、一百萬倍，在真正理解那張開關網路背後的組織原理之前，都沒有用。 ## 兩次“原來我行了”的時刻 訪談快結束時，Lex 問：如果能重歷人生中某個時刻，拋開家庭不談，只挑那個讓你真正快樂、或者深刻改變了你方向的瞬間，會選哪個？ 卡普說自己本科時是個懶學生，研究生第一年也是。 轉折點是他開始做研究的時候。他有過幾個暑期工作，在其中能夠做出貢獻，有了自己的想法。然後是一門關於數學方法和運籌學的課，他把材料整個吞了下去，考分比班上第二名高了 20 分，引起了教師的注意。 > 那讓我意識到，我是有一些能力的，我正在往某個方向走。（理查德·卡普） 另一段回憶關於他父親。 他把 1985 年的圖靈獎演講獻給了父親的記憶。最深的印象是看父親站在黑板前，徒手畫出完美的圓，以及他吸引住那一群參差不齊的八年級學生的能力。 卡普說，他偶爾能溜進父親的教室旁觀。他覺得父親在講臺上狀態最好，整個人活了起來，不只教書，還跟學生閒聊，跟他們打成一片。 他從那裡繼承來的，是強烈的教書願望。 他最近退休，很多以前的學生來了。有的跟他做過研究，有的讀過他的論文，有的上過他的課。他們談論他的時候，不談 1979 年的論文或者 1992 年的論文，談的是從他的課堂裡帶走了什麼。**不是細節，是方法，是教書的姿態。** 他說自己至少在做教員的早年，備課是模範級別的，每次進教室都準備到牙齒。而充分準備帶來的好處，恰恰是能隨時偏離教案。 Lex 問給年輕老師的建議。 卡普說，前三名是：準備、準備、準備。 > 準備給你一種從容，能應對課堂上出現的任何情況。如果你發現一種講法學生沒聽懂，你可以換一種。如果學生提問，你接得住。（理查德·卡普） 準備到位之後，你能跳舞。能換個說法，能換個角度。 還有一件事：讀人。看學生的眼神，從他們的提問裡判斷他們卡在哪裡、接住了什麼。 Lex 問，有沒有哪些電腦科學的思想，是學生一聽就眼睛亮、從此愛上這個領域的？ 卡普說，因人而異。有人幾乎不需要推動，自己在跑，只需要偶爾有個人聽他說。有人需要推一把。有人需要被說服去跟別人合作，而不是單幹。每個人都有自己的起伏，你得把每個學生當人對待，把他最好的一面帶出來。 人類很複雜。他說這句話的時候，語氣很平。 ## 卡普這條線索裡，最該帶走的東西 整場對話裡，卡普反覆在兩個位置上停下來。一個是“我能證明它”，另一個是“它在我這兒跑得很好”。 他一生的工作基本都在這兩個位置之間搭橋。1971 年那篇論文是把橋搭向悲觀的一側：二十一個問題被證明同樣難，誰也別指望僥倖。而拉賓-卡普演算法、SAT 求解器的現實表現、旅行商問題的萬級城市最優解，是把橋搭向樂觀的一側：理論上不該快的東西，在具體輸入上就是快。 這兩側並不矛盾，它們描述的是不同的空間。最壞情況分析劃出的是所有輸入構成的全集，實際應用落在的是全集裡一小塊結構良好的區域。卡普承認後者很難刻畫，甚至公開說自己在這條路上試過、效果不彰。這種承認本身，比任何結論都值得記住。 他對 AI 的判斷也遵循同一個邏輯。他不說深度學習沒用，他說我們沒有理論解釋它為什麼有用，也拿不到洞察。這兩句話可以同時成立，而且同時成立才是準確的描述。 ## 如果這些內容讓你想動手，可以這麼做 - 找一本《演算法導論》或者 Kleinberg-Tardos，把最大流和穩定匹配這兩章讀透。卡普在訪談裡反覆回到這兩個演算法，理由在於它們展示了結構之美與可證明效能同時成立，實用性反而是次要的。 - 拿一個手上真實的排程、匹配、分配問題，先別急著求最優解。用穩定匹配或者匈牙利演算法的思路跑一遍，看看能得到什麼。很多現實問題的“足夠好”解，代價比追求最優低一個數量級。 - 如果你的系統裡有 NP 難問題，去用現成的 SAT 求解器或整數規劃求解器試一遍，別因為它理論上難就直接放棄。數位電路設計和旅行商問題的例項都說明，實際出現的輸入往往比最壞情況友好得多。 - 想感受隨機化的威力，自己實現一遍拉賓-卡普字串匹配，然後在同一份文字上跟 KMP 比一次。讀數不重要，重要的是理解隨機指紋為什麼能讓一個看起來笨的辦法跑得又快又穩。 - 寫程式碼做效能判斷時，把最壞情況和典型情況當成兩個獨立問題來問。演算法最壞情況差，不代表它在你手上的資料上差。反過來，它在你的資料上跑得好，也不代表它在所有資料上都靠得住。 - 如果你在教課或者帶人，把卡普那句話抄下來：準備、準備、準備。準備的目的在換取偏離教案的自由，照本宣科只是它的副產品。 - 找一份講 1971 年那篇《組合問題之間的可歸約性》的講義讀一遍，不必啃原文。搞清楚那 21 個問題怎麼互相歸約，你對“歸約”這個詞會有完全不同的體感。 訪談最後，Lex 唸了阿西莫夫的一句話作為收尾。 > 我不害怕計算機。我害怕的是沒有計算機。（艾薩克·阿西莫夫） 卡普在整場對話裡表達的態度，比這句話更沉一點。他不怕計算機，也不認為計算機會在可見的未來超越人。他更在意另一件事：我們以為自己理解了，其實只是觀察到了效果好。 這兩種擔心，一種指向未來，一種指向現在。後一種更值得花時間。