理查德·卡普
理查德·曼宁·卡普（英语：Richard Manning Karp，1935年1月3日—）是一名美国计算机科学家和计算理论家。他因在计算理论方面的研究而知名，并于1985年获得图灵奖，2004年获得班杰明·富兰克林计算机和认知科学奖，2008年获得京都奖[2]。
| 理查德·卡普 Richard Karp | |
|---|---|
 摄于2009年 | |
| 出生 | Richard Manning Karp 1935年1月3日  美国麻萨诸塞州波士顿 |
| 母校 | 哈佛大学 |
| 知名于 | 安德拉-卡普-罗森堡猜想 埃德蒙兹-卡普演算法 赫尔德-卡普算法 霍普克洛夫特-卡普演算法 卡马卡尔-卡普算法 拉宾-卡普算法 卡普-利普顿定理 卡普的21个NP-完全问题 向量加法系统 |
| 奖项 | 富尔克森奖（1979） 图灵奖（1985） 约翰·冯纽曼理论奖（1990） IEEE计算机协会查尔斯·巴贝奇奖（1995） 美国国家科学奖章（1996） 哈维奖（1998） EATCS奖（2000） 班杰明·富兰克林奖章（2004） 京都奖（2008） |
| 科学生涯 | |
| 研究领域 | 计算机科学 |
| 机构 | 加利福尼亚大学柏克莱分校 IBM |
| 论文 | Some Applications of Logical Syntax to Digital Computer Programming（1959年） |
| 博士导师 | 安东尼·奥廷格[1] |
| 博士生 | 费丝·艾伦 莎莉·佛洛伊德 菲利普·吉邦斯 丹·古斯菲尔德 纳伦德拉·卡尔玛卡尔 薇乐莉·金 迈克尔·卢比 拉耶夫·莫特瓦尼 诺姆·尼散 雷蒙·雷特 汤玛斯·杰罗姆·谢弗 罗恩·沙米尔 芭芭拉·西蒙斯 邢波 诺曼·查德[1] |
由于在NP完备性的理论和应用、构建高效组合算法以及在计算机科学中应用概率方法方面的重大贡献，卡普于1992年获选为美国国家工程院院士。
生平
卡普于1935年1月3日出生于麻萨诸塞州波士顿的犹太裔家庭[3]，父亲是亚伯拉罕·卡普（Abraham Karp），母亲是萝丝·卡普（Rose Karp）。他有三个弟妹，分别是罗伯特（Robert）、大卫和卡罗琳（Carolyn）。他在当时主要是犹太人的波士顿多尔切斯特社区的一个小公寓里长大。
卡普的父母都是哈佛大学的毕业生（他的母亲在参加夜校课程后，最终在57岁时获得哈佛大学的学位），而他的父亲在哈佛大学毕业后曾有过就读医学院的野心，但由于无力支付医学院的学费而成为一名数学教师[3]。卡普就读于哈佛大学，1955年获得学士学位，1956年获得硕士学位，1959年获得应用数学博士学位。之后他开始在IBM的托马斯·J·沃森研究中心工作。
1968年，卡普成为加利福尼亚大学柏克莱分校的计算机科学、数学和运筹学教授。他是电子工程和计算机科学系内计算机科学部的首位副主席[4]。除了在华盛顿大学担任过4年的教授外，他一直居住在柏克莱。1988年至1995年和1999年至今，他还在柏克莱的国际计算机科学研究所担任研究科学家，目前他在那里领导算法组。
卡普被授予美国国家科学奖章，并因其在计算复杂性方面的见解而获得以色列理工学院的哈维奖和2004年班杰明·富兰克林计算机和认知科学奖。1994年，他获选为计算机协会的会士。2002年，他获选为运筹学和管理科学研究所的研究员[5]。他是多个荣誉学位的获得者，也是美国国家科学院[6]、美国文理科学院[7]和美国哲学会[8]的成员。
2012年，卡普成为加利福尼亚大学柏克莱分校西蒙斯计算理论研究所的创始主任[9]。
研究工作
卡普在计算机科学、组合算法和运筹学方面有许多重要发现。他目前的主要研究兴趣包括生物资讯学。
1962年，他与迈克尔·赫尔德（Michael Held）共同开发了赫尔德-卡普算法，这是一种针对旅行推销员问题的精确指数时间算法。
1971年，他与杰克·埃德蒙兹共同开发了埃德蒙兹-卡普演算法，用于解决网路上的最大流问题。1972年，他发表一篇在复杂性理论中具有里程碑意义的论文《组合问题中的可减少性》，其中他证明了21个NP-完全问题[10]。
1973年，他和约翰·霍普克罗夫特发表了霍普克洛夫特-卡普算法，这是已知的在二分图中寻找最大势匹配的最快方法。
1980年，卡普与理查德·利普顿一起证明了卡普-利普顿定理。该定理证明，如果布尔可满足性问题可以由具有多项式逻辑闸数量的布尔电路来解决，那么多项式谱系就会坍缩到其第二层。
图灵奖
他对（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]. （原始内容存档于2016-03-04）.
- ^ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, [2019-10-09], （原始内容存档于2019-05-10）
- ^ Richard M. Karp. www.nasonline.org. [2022-02-22]. （原始内容存档于2023-06-07）.
- ^ Richard M. Karp. American Academy of Arts & Sciences. [2022-02-22]. （原始内容存档于2023-06-07） （英语）.
- ^ APS Member History. search.amphilsoc.org. [2022-02-22]. （原始内容存档于2023-06-07）.
- ^ California Chosen as Home for Computing Institute. The New York Times. 30 April 2012 [23 October 2016]. （原始内容存档于2023-06-07）.
- ^ Richard M. Karp. Reducibility Among Combinatorial Problems (PDF). R. E. Miller; J. W. Thatcher (编). Complexity of Computer Computations. New York: Plenum. 1972: 85–103 [2023-06-07]. （原始内容 (PDF)存档于2011-06-29）.
- ^ 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