理查德·卡普

维基百科,自由的百科全书
理查德·卡普
Richard Karp
攝於2009年
出生Richard Manning Karp
(1935-01-03) 1935年1月3日88歲)
 美國麻薩諸塞州波士頓
母校哈佛大學
知名于安德拉-卡普-羅森堡猜想英语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). 

外部連結[编辑]