分享

Richard Manning Karp(01/03/1935–)

图灵奖获得时间：

1985年。 第二十位图灵奖(1985年)获得者。

图灵奖引用(Turing Award Citation) ：

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.

【笔者译：】

( 授予Richard M. Karp图灵奖以表彰其在) 算法理论方面的持续性的贡献，其中包括在网络流(network flow) 和其他组合优化问题领域的高效算法的研究，在多项式时间可计算性算法方面，特别是对NP完全理论的贡献。Karp引入了现已经成为标准方法的用来证明一个问题是否是属于NP完全。Karp的方法使得许多理论和实际问题被确认为从可计算性角度而言是复杂的或困难的。

【笔者注：】

关于NP完全性问题，可参见：

http://en.wikipedia.org/wiki/NP-complete 

关于各种计算复杂性问题的关系图，可参阅：

http://en.wikipedia.org/wiki/Complexity_class 

Richard 1972年发表了其一篇重要的关于NP完全性的文章：

“Reducibility Among Combinatorial Problems”。这篇文章证明了许多当时研究的组合算法问题是NP完全性的问题，包括：CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE (both directed and undirected versions), 3-DIMENSIONAL MATCHING, KNAPSACK, and PARTITION等等著名的问题。

Richard的论文可参见：

Reducibility Among Combinatorial Problems

Turing Award Lecture(图灵奖演讲文章)：

Combinatorics, Complexity, and Randomness. Commun. ACM 29(2): 97-109(1986)

Richard Karp简介:

Richard Karp Wiki: http://en.wikipedia.org/wiki/Richard_M._Karp 

ACM Crossroads magazine interview/bio of Richard Karp 

Karp’s Home Page at Berkeley

Richard M. Karp生于1935年波士顿，美国。

在哈佛大学，1955年，Richard获得其应用数学学士学位，1956年数学硕士学位，1959年博士学位。

然后，Richard加入IBM Thomas J. Waston研究中心。1968年，Richard加入UC Berkeley出任计算机科学，数学和运筹学的教授。其间，除了在华盛顿大学(University of Washington)担任过4年的教授之外，Richard一直在UC Berkeley工作。关于Richard更为相信的工作背景介绍可参见：http://www.eecs.berkeley.edu/~karp/employment.html

1971年，Richard逾Jack Edmonds合作，提出了Edmonds-Karp算法用来解决网络中的max-flow问题。1987年，逾Michael O. Rabin(1976年图灵奖获得者)合作，提出了Rabin-Karp字符串查找算法。

关于Edmonds-Karp算法：

http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm

关于Robin-Karp算法：

http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

Richard除了在计算机科学方面的卓越贡献之外，在组合算法的运筹学领域也做出了重要的科研贡献。

目前，Richard的主要研究方向是生物信息计算领域。

Richard Karp照片:

分享