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

理察·卡普
Richard Karp
攝於2009年
出生Richard Manning Karp
(1935-01-03) 1935年1月3日89歲)
 美國麻薩諸塞州波士頓
母校哈佛大學
知名於安德拉-卡普-羅森堡猜想英語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]

由於在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). 

外部連結

編輯