热门问题
时间线
聊天
视角
理查德·卡普
来自维基百科，自由的百科全书
Remove ads
理查德·曼宁·卡普（英语：Richard Manning Karp，1935年1月3日—）是一名美国计算机科学家和计算理论家。他因在计算理论方面的研究而知名，并于1985年获得图灵奖，2004年获得本杰明·富兰克林计算机和认知科学奖，2008年获得京都奖[2]。
由于在NP完备性的理论和应用、构建高效组合算法以及在计算机科学中应用概率方法方面的重大贡献，卡普于1992年获选为美国国家工程院院士。
Remove ads
生平
卡普于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]。
Remove ads
研究工作
卡普在计算机科学、组合算法和运筹学方面有许多重要发现。他目前的主要研究兴趣包括生物资讯学。
1962年，他与迈克尔·赫尔德（Michael Held）共同开发了赫尔德-卡普算法，这是一种针对旅行推销员问题的精确指数时间算法。
1971年，他与杰克·埃德蒙兹共同开发了埃德蒙兹-卡普算法，用于解决网络上的最大流问题。1972年，他发表一篇在复杂性理论中具有里程碑意义的论文《组合问题中的可减少性》，其中他证明了21个NP-完全问题[10]。
1973年，他和约翰·霍普克罗夫特发表了霍普克洛夫特-卡普算法，这是已知的在二分图中寻找最大势匹配的最快方法。
1980年，卡普与理查德·利普顿一起证明了卡普-利普顿定理。该定理证明，如果布尔可满足性问题可以由具有多项式逻辑门数量的布尔电路来解决，那么多项式谱系就会坍缩到其第二层。
Remove ads
他对（1985年）图灵奖的引文[11]如下：
由于他对算法理论的持续贡献，包括对网络流和其他组合优化问题的高效算法的发展，对多项式时间可计算性与算法效率的直观概念的识别，以及最引人注目的对NP完备性理论的贡献。卡普引入了现在证明问题为NP-完备的标准方法，这导致许多理论和实际问题被认定为计算上的困难。
参考资料
外部链接
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads