理查德·卡普

理查德·曼宁·卡普(英语:Richard Manning Karp,1935年1月3日)是一名美国计算机科学家计算理论家。他因在计算理论方面的研究而知名,并于1985年获得图灵奖,2004年获得班杰明·富兰克林计算机和认知科学奖,2008年获得京都奖[2]

理查德·卡普
Richard Karp
摄于2009年
出生Richard Manning Karp
(1935-01-03) 1935年1月3日89岁)
 美国麻萨诸塞州波士顿
母校哈佛大学
知名于安德拉-卡普-罗森堡猜想英语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年获选为美国国家工程院院士。

生平

卡普于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. ^ 1.0 1.1 理查德·卡普数学谱系计画的资料。.
  2. ^ Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology
  3. ^ 3.0 3.1 The Power and Limits of Algorithms页面存档备份,存于互联网档案馆) Richard Manning Karp, Kyoto Prize Address, 2008
  4. ^ Karp, Richard. A Personal View of Computer Science at Berkeley. www2.eecs.berkeley.edu. [1 December 2021]. (原始内容存档于2016-03-04). 
  5. ^ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences, [2019-10-09], (原始内容存档于2019-05-10) 
  6. ^ Richard M. Karp. www.nasonline.org. [2022-02-22]. (原始内容存档于2023-06-07). 
  7. ^ Richard M. Karp. American Academy of Arts & Sciences. [2022-02-22]. (原始内容存档于2023-06-07) (英语). 
  8. ^ APS Member History. search.amphilsoc.org. [2022-02-22]. (原始内容存档于2023-06-07). 
  9. ^ California Chosen as Home for Computing Institute. The New York Times. 30 April 2012 [23 October 2016]. (原始内容存档于2023-06-07). 
  10. ^ 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). 
  11. ^ Association for Computing Machinery. ACM Award Citation/Richard M. Karp. [2010-01-17]. (原始内容存档于2012-07-03). 

外部链接