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（在新窗口打开）