第24回（2008年）受賞者 / 先端技術部門 / 情報科学
image

リチャード・マニング・カープ （Richard Manning Karp）

アメリカ / 1935年1月3日
コンピュータ科学者
カリフォルニア大学バークレー校　ユニバーシティ・プロフェッサー、国際コンピュータ科学研究所　上級研究員

「計算複雑さの理論の発展への根幹的貢献」
実用上重要なコンピュータ処理アルゴリズムを数多く開発するとともにＮＰ完全の理論を確立してアルゴリズムの評価や設計における指導原理に大きな影響を与え、1970年代初頭からの計算複雑さの理論の発展に根幹的な貢献をした。

略歴
1935年
米国マサチューセッツ州ボストン市生まれ
1959年
ハーバード大学　博士号（応用数学）
1959-1968年
IBMトーマス・J・ワトソン研究センター　研究員
1968-1994年
カリフォルニア大学バークレー校　教授
1988-1995年
国際コンピュータ科学研究所　研究員
1995-1999年
ワシントン大学　教授
1999-現在
カリフォルニア大学バークレー校　ユニバーシティ・プロフェッサー、国際コンピュータ科学研究所　上級研究員

主な受賞と栄誉
1979年
ファルカーソン賞、国際数理計画法学会・アメリカ数学会
1985年
チューリング賞、国際計算機学会（ACM）
1986年
優秀ティーチング賞、カリフォルニア大学バークレー校
1996年
アメリカ国家科学賞
1998年
ハーヴェイ賞、テクニオン−イスラエル工科大学
2004年
ベンジャミン・フランクリン・メダル、フランクリン協会
会員：
米国科学アカデミー、米国工学アカデミー、米国芸術科学アカデミー、米国科学振興協会、米国哲学会

主な論文
1971年
The traveling-salesman problem and minimum spanning trees: Part II (Held, M. and Karp, R.). Mathematical Programming 1: 6-25.
1972年
Reducibility among Combinatorial Problems (Miller, R. E. and Thatcher, J. W. eds.). in Proceedings of Complexity of Computer Computations, Plenum Press, New York, 85-103.
1972年
Theoretical improvements in algorithmic efficiency for network flow problems (Edmonds, J. and Karp, R.). Journal of the ACM 19: 248-264.
1979年
Random walks, universal traversal sequences, and the complexity of maze problems (Aleliunas, R., Karp, R. M., Lipton, R., Lovász, L. and Rackoff, C.). 20th Annual Symposium on Foundations of Computer Science : 218-223.
1985年
A fast parallel algorithm for the maximal independent set problem (with Wigderson, A.). Journal of the ACM 32: 762-773.
2003年
Conserved pathways within bacteria and yeast as revealed by global protein network alignment (Kelley, B. P., Sharan, R., Karp, R. M., Sittler, T., Root, D. E., Stockwell, B. R.,and Ideker, T). Proceedings of the National Academy of Sciences 100: 11394-11399.