科學人／NP完備性理論的先驅者：卡普

卡普（Richard Manning Karp, 1935~）是1985年圖靈獎得主，他的研究為計算複雜性理論奠定了基礎，讓我們理解人工智慧（AI）的限制和可能性。因此卡普對理論計算機科學的貢獻間接促成了AI研究和發展更廣闊的格局。1996年，我從台灣飛到美國西雅圖，回到母校華盛頓大學時遇到卡普，聆聽他把計算機理論連結到生物基因工程的構想，令我大開眼界。

卡普出生於美國麻州波士頓，在哈佛大學主修數學，分別於1955年、1956年和1959年獲得學士學位、碩士學位及博士學位。完成學業後在IBM擔任數學家，1968年進入學術界，1968~1994年任職於加州大學柏克萊分校。卡普長期對演算法的理論有所貢獻，為網路流（network flow）和其他組合優化（combinatorial optimization）問題開發出高效演算法，用演算法效率的直觀概念識別多項式時間可計算性，以及最重要的是對NP完備性理論的貢獻。

1974年卡普出版《計算的複雜性》（Complexity of Computation ），並以計算機理論發展出多連接交換網路的演算法。1980年，卡普與李普頓（Richard J. Lipton）發表卡普－李普頓定理，他們證明如果布林可滿足度問題（SAT）可以使用具有多項式邏輯門數的布林電路求解，那麼多項式層次結構就會崩潰。

1995~1999年，我的博士論文指導教授拉索斯卡（Edward Lazowska）邀請卡普到華盛頓大學任教。1999年卡普再回到柏克萊分校。2012年，他在柏克萊分校創立了西蒙斯計算理論研究所，並擔任所長至2017年。在西雅圖這段時間，他把前瞻的理論計算機科學與現實世界的問題聯繫起來，嘗試破解人類遺傳密碼。拉索斯卡如此評論：「卡普是計算機科學的巨人之一，是真正改變該領域方向的人。多年來，他是加州大學柏克萊分校的支柱，他搬到華盛頓大學，原因之一是他能幫助定義位於計算機科學和生物科學介面的新興領域。」

的確，生物科學和計算機科學面臨的終極共同挑戰，是理解人類大腦的機制及其與人類思考的關係。卡普說，計算理論與物理、生物、工程和社會科學之間正發展出一種關係，觀察自然或工程系統的計算要求或能力提供了新的見解和思考方式。直到今日，卡普仍持續探究這種觀點，研究其對量子計算、統計物理學、生物學、數學以及全球資訊網支援的經濟和社會過程的影響。

本專欄感謝中華民國資訊軟體協會、台灣電腦資訊發展館支持

作者／林一平

陽明交通大學華邦講座教授、曾任交通大學副校長。主要研究無線通訊及行動計算，並致力於資訊及通訊的教育推廣。

（本文出自2025.06.25《科學人》網站，未經同意禁止轉載。）