一個證明串起 21 個難題

Lex 念出他寫過的：13 歲第一次接觸平面幾何，就被形式證明的優雅吸引。他轉述 Michael Rabin 學生時代被趕出教室，在走廊上想通「兩個不相交的圓之間最短距離」的故事，說單靠推理就能得出這種結果很優雅；也聊到三角形內角和 180 度的證明。

被問到幾何對他的研究有沒有影響，他說歐氏幾何倒沒有：做線性規劃、整數規劃需要高維的想像，他缺乏那種直覺，更依賴代數；設計演算法時，他把過程想成一步步縮小與最佳解的差距，直到命中終點，並以旅行推銷員問題為例。

Lex 念出他寫過的：Don Knuth 把從計算過程的結構得到審美樂趣的人稱為「geeks」，而他發現自己是這種人，是在第一次看到匈牙利演算法的時候。他講解指派問題（把 n 個男生配給 n 個女生、使總成本最小），以及匈牙利演算法怎麼靠反覆對矩陣的列與行做加減來逼近答案。

他認為自己天生就愛玩數字，會心算四位數乘法、靠反覆加倍數字哄自己入睡；暑假在波士頓近郊海灘度假區的 skee-ball 攤位招攬客人，也靠心算讓同事刮目相看；也談到數學那種單靠推理就能得出鐵證如山的結論的吸引力。

1955 年以博士生身分進哈佛計算實驗室，見過佔滿整個房間的 Mark IV（機器有時故障，真的是因為有蟲飛到開關上），但他從沒用它做過實際的事；實驗室後來添購了一台只有 2000 字儲存空間的 UNIVAC，配置記憶體得靠人工技巧。

他說當年完全沒想過口袋裡會有電腦，只感覺到這是「未來的浪潮」，母親也告訴他資料處理會變得很重要；對圖靈測試，他認為太主觀，不是判斷智能的好方法。

他說目前的成就都在很有限的規則裡做很精確的任務，沒有程式對世界的理解比得上六個月大的嬰兒；他懷疑圖靈機能否達到人類等級的智能，也懷疑「奇點」會發生，理由是語音、機器人、自然語言處理的成就都離人類認知還很遠；即使開關的速度快上千倍甚至百萬倍，沒搞懂那張開關網路的組織原理也沒用。

他從「圖」的定義說起（點與連接點的邊），舉排課表、指派問題、邏輯電路設計這幾種常見的組合最佳化問題為例，說明邊可以有方向、也可以帶權重。

他解釋網路流：邊是運送某種東西的管道、各有容量，要求從起點到終點的最大流量；他說他和 Jack Edmonds 應該是最早正式證明最大流問題能在多項式時間解開的人。他把「多項式時間」定義成計算步驟數量只隨輸入規模的固定次方成長，理論學界拿這個當作「有效率」的判準。

他提到自己和 Edmonds 最早把指派問題做到 n³ 步（之前的演算法要 n⁴）；接著用「找出一群彼此都相鄰的點」的團問題說明 NP：找答案可能很難，但拿到一組答案之後驗證它對不對卻很快，這種「驗證快、求解未必快」的問題就屬於 NP。

他說 P 裡的問題都在 NP 裡，但反過來不一定：拿到一份課表能很快驗證，不代表能很快排出來。被問到願不願意把錢押在 P 是否等於 NP 上，他押不等於，理由是有些問題（例如 Gauss 就研究過的大數因數分解）已經被研究了幾世紀，始終沒人找到有效演算法。

他提到 Stephen Cook 證明命題邏輯的可滿足性問題（SAT）可以表達 NP 裡的任何問題，靠的是圖靈機這個抽象計算模型；看懂這個證明的邏輯不難，但意涵驚人。

Cook 的論文 1971 年在研討會上發表，他看到後意識到 SAT 是通用的組合問題，而且憑經驗覺得還有很多問題有同樣的結構，於是開始找轉換方式：先把 SAT 改寫成只能取 0 或 1 的整數規劃，再示範怎麼把 SAT 轉成獨立集合問題（同一個子句裡的項、互為否定的項之間連邊）。

他在 1971 年的論文裡證明 SAT 能改寫成 21 個常見的裝填、覆蓋、配對等問題中的任何一個；這代表它們表達力相同，不代表計算複雜度相同，只能說要嘛全都能在多項式時間內解、要嘛全都不能。他也說明是非題裡最難的叫 NP-complete，最佳化版本裡最難的叫 NP-hard，稱之為「小小的技術細節」。

他認為不管最後證出 P 等於還是不等於 NP，都要靠現在還沒有的新概念；若 P 不等於 NP（這是大家預期的），意味著多數組合問題無法保證每次都求到最佳解，只能依賴啟發式方法或近似解；不過多數個案也許還是解得出來。

他最喜歡穩定婚配問題：由其中一方依偏好清單逐一提親，另一方可以先暫時接受、之後換更好的人選，直到沒有哪一對想拋下各自的伴侶私奔；他說這跟住院醫師配對這類實際問題有關，但形式不完全一樣。

他指出主動提親的一方結果最好，提親方的每個人都至少跟在其他任何穩定配對裡一樣好；但如果夫妻要分到同一個城市的醫院，加上這種限制，問題就變成 NP-hard。這個演算法出自 Gale 與 Shapley，Gale 來不及分到諾貝爾獎就過世了，Shapley 後來和別人共享諾貝爾經濟學獎。

在以自己命名的幾個演算法（字串比對、最大流、二分圖匹配）裡，他最喜歡 Rabin-Karp 字串搜尋演算法，因為它展現了隨機化的威力：替字串算出一個「指紋」數字，用隨機挑的質數取餘數來快速比對，而不必逐字核對。

他用「隨機抽樣預測選舉結果」與「用 Fermat 小定理快速證明一個數不是質數」當例子，說明隨機演算法就是從某個範圍隨機抽數字、或隨機從集合裡挑東西，而抽樣能代表整體是統計學的基本事實。

他自己設計過一個演算法，估算滿足一組公式中至少一個的解有幾個：想成 0/1 矩陣，依每一列 1 的個數抽列，只有當它是該行最早出現 1 的那一列才算數，避免重複計算；另一個例子是檢查兩個公式是否恆等，隨機代一個值進去，兩者若不同，很可能就會露出不一致。

他指出理論上是 NP-complete 的 SAT 問題，實務上 SAT solver 相當可靠地解出上百萬變數的電路設計問題；旅行推銷員問題也一樣，整數規劃搭配一些技巧能在很短時間內對一兩千座城市求出可證明的最佳解，上萬座城市也辦得到，只是要算好幾個月。

他早年用過度簡化的隨機圖模型研究平均情況表現，例如證明邊數只要比 n log n 多一點，就很可能有 Hamiltonian 迴路，得出許多漂亮結果，但學界反應冷淡，他後來也覺得實用價值不大；他認為理論電腦科學至今仍沒有像監督式學習的訓練集那樣的真實資料可用。

他與 Richard Lipton 在 1979 年的論文問：如果 NP 裡的問題對每一種輸入規模都有「量身訂做的小電路」，會發生什麼事？他們證明這會讓那一層層加上量詞的複雜度階層坍縮到第二層；他說這是 NP 沒有小電路的證據，但只是證據，不是證明。

他認為機器學習的表現評估方式更接近經驗性的 SAT solver 研究，而非理論電腦科學；它在影像處理、機器人、遊戲上都有很大的成功，自然語言處理稍微少一點，但目前沒有理論解釋為什麼類神經網路對訓練集之外的輸入也表現得好，也很難看懂網路內部依據什麼特徵做判斷。

他認為編輯 DNA 的能力令人驚嘆，但牽涉重大倫理問題，尤其是修改生殖細胞會影響所有後代，而假設剔除某個基因一定有益也是一種傲慢；分析基因體資料、找出哪些基因在什麼條件下作用、預測疾病風險，則是統計上的大數據問題。

他最深刻的回憶是父親在黑板前徒手畫出完美的圓，吸引一群國二生的注意；他說從父親身上傳下來的，是很想當老師的那股渴望。他最近退休，來的學生談的不是他 1979 年或 1992 年的論文，而是他上課的方式；他也自豪早年在 Berkeley 備課一絲不苟。

被問到給老師的建議，他答「前三名都是準備」：準備充分才能應付課堂上的任何狀況，一種講法講不通就換另一種，學生提問也接得住；他也說每個學生需要的帶法都不一樣。

他說自己大學和研究所第一年都算是懶散的學生，轉折是開始做研究：暑期工作做出了貢獻，又修了一門作業研究數學方法的課，比班上任何人都高出 20 分，因此引起教授注意，讓他意識到自己有些天分。