图灵奖：理查德·卡普（1985）

图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。”图灵奖”系列将介绍历届获奖者。每周二更新，本文为第 24 期。图灵奖：理查德·卡普（1985）

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

本文来自 wiki:Richard M. Karp，翻译基于 谷歌翻译.

理查德·曼宁·卡普（Richard Manning Karp，1935 年 1 月 3 日出生）是一位美国计算机科学家和计算理论家，因在 NP 完备性理论和应用、构建高效组合算法以及在计算机科学中应用概率方法方面做出的重大贡献而知名。

他于 1985 年获得图灵奖。

其图灵奖颁奖词为“表彰他对算法理论的持续贡献，包括开发网络流和其他组合优化问题的有效算法、用算法效率的直观概念识别多项式时间可计算性，以及最值得注意的是对NP-完整性理论的贡献。Karp 引入了现在的标准方法来证明问题是 NP 完全的，这导致许多理论和实际问题在计算上是困难的。”。（For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.）

生平

Karp 出生于波士顿马萨诸塞州。

他 1955 年于哈佛大学获得学士学位，1956 年获得硕士学位，1959 年获得应用数学博士学位。随后，在 IBM 的 Thomas J. Watson 研究中心开始工作。

1968年，他成为加州大学伯克利分校计算机科学、数学和运筹学教授。

除了在华盛顿大学担任教授四年外，从 1988 年到 1995 年以及 1999 年至今，他一直留在伯克利大学。他还担任伯克利国际计算机科学研究所的研究科学家，目前领导该研究所的算法小组。

2012 年，卡普成为加州大学伯克利分校西蒙斯计算理论研究所的创始主任。

研究工作

• 1962 年，他与 Michael Held 共同开发了 Held-Karp 算法，这是一种针对旅行商问题的精确指数时间算法
• 1971 年，他与 Jack Edmonds 共同开发了 Edmonds-Karp 算法，用于解决网络上的最大流问题，并于 1972 年发表了复杂性理论中具有里程碑意义的论文“组合问题的可归约性”，其中他证明了 21 个问题 NP 完全
• 1973 年，他和 John Hopcroft 发表了 Hopcroft-Karp 算法，这是已知在二部图中查找最大基数匹配的最快方法
• 1980 年，卡普与理查德·J·利普顿 (Richard J. Lipton) 一起证明了卡普-利普顿定理（该定理证明，如果 SAT 可以通过具有多项式逻辑门数的布尔电路来求解，则多项式层次结构会崩溃到第二层）
• 1987 年，他与 Michael O. Rabin 共同开发了 Rabin-Karp 字符串搜索算法

~~

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~

觉得还不错？可以在公众号菜单栏找到“赞赏”入口~