理查德·卡普

理查德·曼寧·卡普（，）是一名美國計算機科學家和計算理論家。他因在計算理論方面的研究而知名，並於1985年獲得圖靈獎，2004年獲得班傑明·富蘭克林計算機和認知科學獎，2008年獲得京都獎Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology。

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

 生平 
卡普於1935年1月3日出生於麻薩諸塞州波士頓的猶太裔家庭The Power and Limits of Algorithms  Richard Manning Karp, Kyoto Prize Address, 2008，父親是亞伯拉罕·卡普（Abraham Karp），母親是蘿絲·卡普（Rose Karp）。他有三個弟妹，分別是羅伯特（Robert）、和卡羅琳（Carolyn）。他在當時主要是猶太人的波士頓社區的一個小公寓裡長大。

卡普的父母都是哈佛大學的畢業生（他的母親在參加夜校課程後，最終在57歲時獲得哈佛大學的學位），而他的父親在哈佛大學畢業後曾有過就讀醫學院的野心，但由於無力支付醫學院的學費而成為一名數學教師。卡普就讀於哈佛大學，1955年獲得學士學位，1956年獲得碩士學位，1959年獲得應用數學博士學位。之後他開始在IBM的工作。

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

卡普被授予美國國家科學獎章，並因其在計算複雜性方面的見解而獲得以色列理工學院的和2004年班傑明·富蘭克林計算機和認知科學獎。1994年，他獲選為計算機協會的會士。2002年，他獲選為的研究員。他是多個榮譽學位的獲得者，也是美國國家科學院、美國文理科學院和美國哲學會的成員。

2012年，卡普成為加利福尼亞大學柏克萊分校的創始主任。

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

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

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

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

1980年，卡普與一起證明了。該定理證明，如果布爾可滿足性問題可以由具有多項式邏輯閘數量的來解決，那麼多項式譜系就會坍縮到其第二層。

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

 圖靈獎 
他對（1985年）圖靈獎的引文如下：

 參考資料 

 外部連結 

 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

Category:美國計算機科學家
Category:理論計算機科學家
Category:20世紀美國工程師
Category:20世紀美國數學家
Category:21世紀美國數學家
Category:20世紀美國科學家
Category:21世紀美國科學家
Category:猶太裔美國科學家
Category:波士頓人
Category:哈佛大學校友
Category:加州大學柏克萊分校教師
Category:圖靈獎獲得者
Category:美國國家科學獎獲獎者
Category:富蘭克林研究所班傑明·富蘭克林獎章獲得者
Category:京都獎獲得者
Category:美國計算機學會會士
Category:美國國家工程院院士
Category:美國國家科學院院士
Category:美國哲學學會會士
Category:法蘭西科學院院士