理查德·卡普

{{Infobox scientist
| name = 理查德·卡普
Richard Karp
| image = Karp mg 7725-b.cr2.jpg
| image_size =
| caption = 攝於2009年
| birth_name = Richard Manning Karp
| birth_date =
| birth_place = 麻薩諸塞州波士頓
| death_date =
| death_place =
| alma_mater = 哈佛大學
| known_for =
埃德蒙茲-卡普演算法

霍普克洛夫特-卡普演算法

拉賓-卡普算法

卡普的21個NP-完全問題

| prizes = 富爾克森獎（1979）
圖靈獎（1985）
（1990）
（1995）
美國國家科學獎章（1996）
（1998）
（2000）
班傑明·富蘭克林獎章（2004）
京都獎（2008）
| field = 計算機科學
| work_institution = 加利福尼亞大學柏克萊分校
IBM
| thesis_title = Some Applications of Logical Syntax to Digital Computer Programming
| thesis_year = 1959年
| doctoral_advisor =
| doctoral_students =

諾姆·尼散

邢波
。

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

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

卡普的父母都是哈佛大學的畢業生（他的母親在參加夜校課程後，最終在57歲時獲得哈佛大學的學位），而他的父親在哈佛大學畢業後曾有過就讀醫學院的野心，但由於無力支付醫學院的學費而成為一名數學教師。除了在華盛頓大學擔任過4年的教授外，他一直居住在柏克萊。1988年至1995年和1999年至今，他還在柏克萊的擔任研究科學家，目前他在那裡領導算法組。

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

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

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

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

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

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

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

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

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

參考資料
外部連結

• [https://web.archive.org/web/20100420002246/http://www.acm.org/crossroads/dayinlife/bios/richard_karp.html ACM Crossroads magazine interview/bio of Richard Karp]
• [http://www.eecs.berkeley.edu/Faculty/Homepages/karp.html Karp's Home Page at Berkeley]
• [https://www.informs.org/content/view/full/272029 Biography of Richard Karp] from the Institute for Operations Research and the Management Sciences