富爾克森獎（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）
卡普於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）工作。
^ 3.03.1The Power and Limits of Algorithms Richard Manning Karp, Kyoto Prize Address, 2008
^Karp, Richard. A Personal View of Computer Science at Berkeley. www2.eecs.berkeley.edu. [1 December 2021].
^Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, [2019-10-09]
^Richard M. Karp. www.nasonline.org. [2022-02-22].
^Richard M. Karp. American Academy of Arts & Sciences. [2022-02-22]（英语）.
^APS Member History. search.amphilsoc.org. [2022-02-22].
^California Chosen as Home for Computing Institute. The New York Times. 30 April 2012 [23 October 2016].
^Richard M. Karp. Reducibility Among Combinatorial Problems (PDF). R. E. Miller; J. W. Thatcher (编). Complexity of Computer Computations. New York: Plenum. 1972: 85–103.
^Association for Computing Machinery. ACM Award Citation/Richard M. Karp. [2010-01-17]. （原始内容存档于2012-07-03）.
Biography of Richard Karp from the Institute for Operations Research and the Management Sciences
七月 29, 2023
理查德, 卡普, 理查德, 曼寧, 卡普, 英語, richard, manning, karp, 1935年1月3日, 是一名美國計算機科學家和計算理論家, 他因在計算理論方面的研究而知名, 並於1985年獲得圖靈獎, 2004年獲得班傑明, 富蘭克林計算機和認知科學獎, 2008年獲得京都獎, richard, karp攝於2009年出生richard, manning, karp, 1935, 1935年1月3日, 88歲, 美國麻薩諸塞州波士頓母校哈佛大學知名于安德拉, 卡普, 羅森堡猜想, 英语, aan. 理查德 曼寧 卡普 英語 Richard Manning Karp 1935年1月3日 是一名美國計算機科學家和計算理論家 他因在計算理論方面的研究而知名 並於1985年獲得圖靈獎 2004年獲得班傑明 富蘭克林計算機和認知科學獎 2008年獲得京都獎 2 理查德 卡普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 由於在NP完備性的理論和應用 構建高效組合算法以及在計算機科學中應用概率方法方面的重大貢獻 卡普於1992年獲選為美國國家工程院院士 目录 1 生平 2 研究工作 2 1 圖靈獎 3 參考資料 4 外部連結生平 编辑卡普於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 0 1 1 理查德 卡普在數學譜系計畫的資料 Richard Manning Karp THE 2008 KYOTO PRIZE Advanced Technology 3 0 3 1 The Power and Limits of Algorithms Richard Manning Karp Kyoto Prize Address 2008 Karp Richard A Personal View of Computer Science at Berkeley www2 eecs berkeley edu 1 December 2021 Fellows Alphabetical List Institute for Operations Research and the Management Sciences 2019 10 09 Richard M Karp www nasonline org 2022 02 22 Richard M Karp American Academy of Arts amp Sciences 2022 02 22 英语 APS Member History search amphilsoc org 2022 02 22 California Chosen as Home for Computing Institute The New York Times 30 April 2012 23 October 2016 Richard M Karp Reducibility Among Combinatorial Problems PDF R E Miller J W Thatcher 编 Complexity of Computer Computations New York Plenum 1972 85 103 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 取自 https zh wikipedia org w index php title 理查德 卡普 amp oldid 77584879, 维基百科，wiki，书籍，书籍，图书馆，
