ABAB Pedia
詞條廣場

Richard Karp

Richard Karp是美國理論計算機科學家、UC BerkeleyUniversity of California, BerkeleyUniversity of California, Berkeley（加州大學伯克利分校，UC Berkeley）是University of California系統的成員校，其前身University of California於1868年由兩校合併創立，1873年遷至加利福尼亞州伯克利。點擊查看完整詞條榮休教授，以1972年證明21個組合問題為NP完全及Edmonds-Karp等算法著稱，獲1985年ACMAustralian Community MediaAustralian Community Media（ACM）是澳大利亞地區與鄉村新聞出版集團，旗下有The Canberra Times等逾100個品牌；2019年Nine將其出售給由Antony Catalano與Thorney Investment Group相關方控制的公司。點擊查看完整詞條圖靈獎，並曾任Simons Institute for the Theory of Computing創始主任。

本頁目錄25 節
詞條資料

1935年1月3日出生於Boston

Richard Manning Karp於1935年1月3日生於馬薩諸塞州Boston。⁠[1]

他是家中四個孩子中的長子，父親是一名初中教師。⁠[2]

1940年代童年與Boston Latin School

他自幼喜愛數學，能心算四位數乘法，上十年級時曾裝病在家解幾何題。⁠[3]

他在Boston Latin School接受古典教育，學了六年拉丁語。⁠[4]

1955—1959年Harvard學位與計算實驗室

他於1955年獲HarvardHarvard UniversityHarvard University（哈佛大學）是位於美國馬薩諸塞州的私立研究型大學，1636年由馬薩諸塞灣殖民地議會批准設立，1639年以早期捐助人 John Harvard 命名。學校以劍橋、波士頓 Allston 和 Longwood 為主要校區，設 Harvard College、本科以外的專業與研究生學院及 Radcliffe 高等研究院。學校由 Harvard Corporation 與 Board of Overseers 兩個治理機構共同履職；截至2026年10月，校長為 Alan M. Garber。2025財年末捐贈基金規模為569億美元。點擊查看完整詞條數學學士學位，1956年獲應用數學碩士學位，1959年獲應用數學博士學位。⁠[5]

他的博士論文由Anthony G. Oettinger指導，研究用圖論算法分析程序。⁠[2]

1959—1968年任職IBM研究部門

1959至1968年，他在IBM Thomas J. Watson Research Center工作，與Ray Miller、Michael Held等人研究並行計算模型和旅行商問題等組合問題。⁠[3]

這一時期他還曾在New York University、University of MichiganUniversity of MichiganUniversity of Michigan（密歇根大學）是1817年在底特律創立、1837年遷至密歇根州安娜堡的大學，由經全州選舉產生的董事會治理，另設Dearborn與Flint校區。點擊查看完整詞條和Polytechnic Institute of Brooklyn任職。⁠[6]

1968年加入UC Berkeley

他於1968年加入UC Berkeley，此後在那裡建立以理論計算機科學為中心的研究重鎮，指導了大量年輕學者，在並行算法與概率算法理論的建立中起了主導作用。⁠[7]

1971—1972年NP完全性理論

1971年，他讀到Steve Cook關於命題可滿足性問題的論文，受其啟發發展出NP完全性的概念；1972年，他與Jack Edmonds提出計算網絡最大流的Edmonds-Karp算法。⁠[2]

1972年4月，他在IBM的一次研討會上向大批聽眾報告NP完全性成果，此前首次相關演講是在Don KnuthDonald KnuthDonald Knuth（高德納）是美國計算機科學家和數學家、Stanford University榮休教授，多卷本《The Art of Computer Programming》的作者和TeX排版系統的創造者，被稱為算法分析之父。點擊查看完整詞條家中的討論會上。⁠[4]

1972年發表《Reducibility Among Combinatorial Problems》

他在1972年的論文“Reducibility Among Combinatorial Problems”中證明了21個問題是NP完全的，這些問題是眾多應用中的常見計算問題。⁠[3]

1972—1974年首任計算機科學分部主任

1972年Berkeley將兩個計算機科學教師群體合併為EECS系下的計算機科學分部，他作為妥協人選勉強出任負責人兩年。⁠[4]

1977年獲Lanchester Prize

他於1977年獲INFORMS Frederick W. Lanchester Prize。⁠[5]

1985年獲圖靈獎

他獲1985年ACM圖靈獎，表彰他對算法理論的持續貢獻，包括網絡流等組合優化問題的高效算法、將多項式時間可計算性與算法效率等同，以及NP完全性理論。⁠[8]

1985—1986年組織MSRI計算複雜性年

1985—1986學年，他在Berkeley的Mathematical Sciences Research Institute聯合組織了計算複雜性年。⁠[1]

1988年加入ICSI

1988至1995年，他在Berkeley的International Computer Science Institute任研究科學家，1999年起再度在該所任職。⁠[9]

1990年獲John von Neumann Theory Prize

他於1990年獲INFORMS John von Neumann Theory Prize。⁠[5]

1995年轉往University of Washington

他於1995年加入University of Washington，與分子生物技術系主任Leroy Hood合作，研究破譯人類遺傳密碼。⁠[10]

1996年7月26日獲美國國家科學獎章

他從Bill Clinton總統手中接過1996年度美國國家科學獎章；他稱這是自己獲得的“most significant award”（最重要的獎項）。⁠[10]

1999年重返Berkeley

1999年起他重新在UC Berkeley任教，並曾任Class of 1939 Chair與University Professor。⁠[11]

2004年獲Benjamin Franklin Medal

Franklin Institute授予他Benjamin FranklinBenjamin FranklinBenjamin Franklin（本傑明·富蘭克林，1706年1月17日—1790年4月17日）是北美殖民地與美國建國時期的印刷商、出版人、科學家、外交家和政治家，美國開國元勳之一。他在費城經營《Pennsylvania Gazette》並出版《Poor Richard's Almanack》，創辦北美首家借閱圖書館，倡議創辦後來的賓夕法尼亞大學；他以電學實驗和避雷針等發明聞名，曾任美國首任郵政總長，參與起草《獨立宣言》，在法國簽訂美法條約，並簽署結束獨立戰爭的《巴黎條約》。點擊查看完整詞條 Medal，以表彰他對理解計算複雜性的貢獻。⁠[6]

2008年6月20日獲京都獎

稻盛財團（Inamori Foundation）宣佈他獲2008年京都獎尖端技術部門獎，獎金5,000萬日元；當時他是Berkeley的University Professor，在數學、生物工程及工業工程與運籌學系兼任。⁠[12]

2012年5月1日出任Simons Institute創始主任

Simons Foundation宣佈向Berkeley撥款6,000萬美元設立Simons Institute for the Theory of Computing，由他任創始主任，Alistair Sinclair與Christos Papadimitriou分任副主任與首席科學家。⁠[13]

2013年Simons Institute開始運作

他在主任信中宣佈，研究所於2013年2月舉辦首次科學會議，並於同年8月在翻修後的Calvin Lab開始首個全面運行的學期。⁠[14]

2017年12月31日卸任Simons Institute主任

五年任期結束後，他於2017年12月31日卸任Simons Institute主任，由Shafi Goldwasser接任。⁠[15]

2019年Richard M. Karp Fund與系列講座

在他第三次（也可能是最後一次）從Berkeley退休之際，Simons Institute以他之名發起籌款，並設立Richard M. Karp Distinguished Lectures；該講座與Calvin Lab內紀念他貢獻的永久展陳於2019年秋推出。⁠[16]

2020年7月26日做客Lex Fridman Podcast

他做客Lex FridmanLex FridmanLex Fridman 是生於蘇聯、在美國長大的計算機科學家和播客主持人，任 MIT 研究科學家，研究人機交互與自動駕駛。他主持的 Lex Fridman Podcast 以數小時長篇對話著稱，嘉賓包括多國領導人和科技企業領袖。點擊查看完整詞條 Podcast第111期，談及幾何、算法可視化、Don Knuth、Edmonds-Karp算法、P與NP、穩定婚姻問題、隨機算法、機器學習與生物信息學等話題。⁠[17]

關聯機構、網站與公開賬號

UC Berkeley：官網：https://www.berkeley.edu/（在新窗口打開）⁠[18]

International Computer Science Institute：官網：https://www.icsi.berkeley.edu/（在新窗口打開）⁠[19]

Simons Institute for the Theory of Computing：官網：https://simons.berkeley.edu/（在新窗口打開）⁠[20]

來源

  1. Title: What Makes an Algorithm Great?（在新窗口打開）
  2. Karp, Richard M. - INFORMS（在新窗口打開）
  3. Science Lives: Computer Scientist Richard Karp – Simons Foundation（在新窗口打開）
  4. The Mysteries of Algorithms（在新窗口打開）
  5. Richard M. Karp | EECS at UC Berkeley（在新窗口打開）
  6. Richard M. Karp | The Franklin Institute（在新窗口打開）
  7. Richard Manning Karp | Kyoto Prize（在新窗口打開）
  8. Richard M. Karp | Berkeley in the 80s（在新窗口打開）
  9. Richard Karp | Center for Computational Biology（在新窗口打開）
  10. UW computer scientist awarded National Medal of Science（在新窗口打開）
  11. Richard Karp（在新窗口打開）
  12. Richard Karp, renowned computer theorist, wins 2008 Kyoto Prize（在新窗口打開）
  13. Simons Foundation awards UC Berkeley $60 million for theory of computing institute | Research UC Berkeley（在新窗口打開）
  14. Letter from the Director（在新窗口打開）
  15. Oral History: Russell Impagliazzo in Conversation with Dick Karp（在新窗口打開）
  16. Richard M. Karp Fund（在新窗口打開）
  17. #111 - Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast（在新窗口打開）
  18. University of California, Berkeley: Home（在新窗口打開）
  19. ICSI（在新窗口打開）
  20. Simons Institute for the Theory of Computing（在新窗口打開）