理查德·卡普

理查德·卡普 Richard Karp
攝於2009年
出生	Richard Manning Karp (1935-01-03) 1935年1月3日（90歲）  美国麻薩諸塞州波士頓
母校	哈佛大學
知名于	安德拉-卡普-羅森堡猜想（英语：Aanderaa–Karp–Rosenberg conjecture） 埃德蒙茲-卡普演算法 赫爾德-卡普算法（英语：Held–Karp algorithm） 霍普克洛夫特-卡普演算法 卡馬卡爾-卡普算法（英语：Largest differencing method） 拉賓-卡普算法 卡普-利普頓定理（英语：Karp–Lipton theorem） 卡普的21個NP-完全問題 向量加法系統（英语：Vector addition system）
奖项	富爾克森獎（1979） 圖靈獎（1985） 約翰·馮紐曼理論獎（英语：John von Neumann Theory Prize）（1990） IEEE計算機協會查爾斯·巴貝奇獎（英语：International Parallel and Distributed Processing Symposium）（1995） 美國國家科學獎章（1996） 哈維獎（英语：Harvey Prize）（1998） EATCS獎（英语：European Association for Theoretical Computer Science）（2000） 班傑明·富蘭克林獎章（2004） 京都獎（2008）
科学生涯
研究领域	計算機科學
机构	加利福尼亞大學柏克萊分校 IBM
论文	Some Applications of Logical Syntax to Digital Computer Programming（1959年）
博士導師	安東尼·奧廷格（英语：Anthony Oettinger）[1]
博士生	費絲·艾倫（英语：Faith Ellen） 莎莉·佛洛伊德（英语：Sally Floyd） 菲利普·吉邦斯（英语：Phillip Gibbons） 丹·古斯菲爾德（英语：Dan Gusfield） 納倫德拉·卡爾瑪卡爾（英语：Narendra Karmarkar） 薇樂莉·金（英语：Valerie King） 邁克爾·盧比（英语：Michael Luby） 拉耶夫·莫特瓦尼（英语：Rajeev Motwani） 諾姆·尼散 雷蒙·雷特（英语：Raymond Reiter） 湯瑪斯·傑羅姆·謝弗（英语：Thomas Jerome Schaefer） 羅恩·沙米爾（英语：Ron Shamir） 芭芭拉·西蒙斯（英语：Barbara Simons） 邢波 諾曼·查德（英语：Norman Zada）[1]

理查德·曼寧·卡普（英語：Richard Manning Karp，1935年1月3日—）是一名美國計算機科學家和計算理論家。他因在計算理論方面的研究而知名，並於1985年獲得圖靈獎，2004年獲得班傑明·富蘭克林計算機和認知科學獎，2008年獲得京都獎^[2]。

由於在NP完備性的理論和應用、構建高效組合算法以及在計算機科學中應用概率方法方面的重大貢獻，卡普於1992年獲選為美國國家工程院院士。

卡普於1935年1月3日出生於麻薩諸塞州波士頓的猶太裔家庭^[3]，父親是亞伯拉罕·卡普（Abraham Karp），母親是蘿絲·卡普（Rose Karp）。他有三個弟妹，分別是羅伯特（Robert）、大衛（英语：David A. Karp）和卡羅琳（Carolyn）。他在當時主要是猶太人的波士頓多爾切斯特（英语：Dorchester, Boston）社區的一個小公寓裡長大。

卡普的父母都是哈佛大學的畢業生（他的母親在參加夜校課程後，最終在57歲時獲得哈佛大學的學位），而他的父親在哈佛大學畢業後曾有過就讀醫學院的野心，但由於無力支付醫學院的學費而成為一名數學教師^[3]。卡普就讀於哈佛大學，1955年獲得學士學位，1956年獲得碩士學位，1959年獲得應用數學博士學位。之後他開始在IBM的托馬斯·J·沃森研究中心（英语：Thomas J. Watson Research Center）工作。

1968年，卡普成為加利福尼亞大學柏克萊分校的計算機科學、數學和運籌學教授。他是電子工程和計算機科學系內計算機科學部的首位副主席^[4]。除了在華盛頓大學擔任過4年的教授外，他一直居住在柏克萊。1988年至1995年和1999年至今，他還在柏克萊的國際計算機科學研究所（英语：International Computer Science Institute）擔任研究科學家，目前他在那裡領導算法組。

卡普被授予美國國家科學獎章，並因其在計算複雜性方面的見解而獲得以色列理工學院的哈維獎（英语：Harvey Prize）和2004年班傑明·富蘭克林計算機和認知科學獎。1994年，他獲選為計算機協會的會士。2002年，他獲選為運籌學和管理科學研究所（英语：Institute for Operations Research and the Management Sciences）的研究員^[5]。他是多個榮譽學位的獲得者，也是美國國家科學院^[6]、美國文理科學院^[7]和美國哲學會^[8]的成員。

2012年，卡普成為加利福尼亞大學柏克萊分校西蒙斯計算理論研究所（英语：Simons Institute for the Theory of Computing）的創始主任^[9]。

卡普在計算機科學、組合算法和運籌學方面有許多重要發現。他目前的主要研究興趣包括生物資訊學。

1962年，他與邁克爾·赫爾德（Michael Held）共同開發了赫爾德-卡普算法（英语：Held–Karp algorithm），這是一種針對旅行推銷員問題的精確指數時間算法。

1971年，他與傑克·埃德蒙茲（英语：Jack Edmonds）共同開發了埃德蒙茲-卡普演算法，用於解決網路上的最大流問題。1972年，他發表一篇在複雜性理論中具有里程碑意義的論文《組合問題中的可減少性》，其中他證明了21個NP-完全問題^[10]。

1973年，他和約翰·霍普克羅夫特發表了霍普克洛夫特-卡普算法，這是已知的在二分圖中尋找最大勢匹配的最快方法。

1980年，卡普與理查德·利普頓（英语：Richard Lipton）一起證明了卡普-利普頓定理（英语：Karp–Lipton theorem）。該定理證明，如果布爾可滿足性問題可以由具有多項式邏輯閘數量的布爾電路（英语：Boolean circuit）來解決，那麼多項式譜系就會坍縮到其第二層。

1987年，他與迈克尔·拉宾共同開發了拉賓-卡普演算法。

他對（1985年）圖靈獎的引文^[11]如下：

由於他對算法理論的持續貢獻，包括對網路流和其他組合優化問題的高效算法的發展，對多項式時間可計算性與算法效率的直觀概念的識別，以及最引人注目的對NP完備性理論的貢獻。卡普引入了現在證明問題為NP-完備的標準方法，這導致許多理論和實際問題被認定為計算上的困難。

1. ^ ^{1.0 1.1} 理查德·卡普在數學譜系計畫的資料。.
2. ^ Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology
3. ^ ^{3.0 3.1} The Power and Limits of Algorithms （页面存档备份，存于互联网档案馆） Richard Manning Karp, Kyoto Prize Address, 2008
4. ^ Karp, Richard. A Personal View of Computer Science at Berkeley. www2.eecs.berkeley.edu. [1 December 2021]. （原始内容存档于2016-03-04）. 
5. ^ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, [2019-10-09], （原始内容存档于2019-05-10） 
6. ^ Richard M. Karp. www.nasonline.org. [2022-02-22]. （原始内容存档于2023-06-07）. 
7. ^ Richard M. Karp. American Academy of Arts & Sciences. [2022-02-22]. （原始内容存档于2023-06-07） （英语）. 
8. ^ APS Member History. search.amphilsoc.org. [2022-02-22]. （原始内容存档于2023-06-07）. 
9. ^ California Chosen as Home for Computing Institute. The New York Times. 30 April 2012 [23 October 2016]. （原始内容存档于2023-06-07）. 
10. ^ Richard M. Karp. Reducibility Among Combinatorial Problems (PDF). R. E. Miller; J. W. Thatcher (编). Complexity of Computer Computations. New York: Plenum. 1972: 85–103 [2023-06-07]. （原始内容 (PDF)存档于2011-06-29）. 
11. ^ Association for Computing Machinery. ACM Award Citation/Richard M. Karp. [2010-01-17]. （原始内容存档于2012-07-03）. 

维基共享资源上的相关多媒体资源：理查德·卡普

• ACM Crossroads magazine interview/bio of Richard Karp
• Karp's Home Page at Berkeley （页面存档备份，存于互联网档案馆）
• Biography of Richard Karp （页面存档备份，存于互联网档案馆） from the Institute for Operations Research and the Management Sciences