受賞者
リチャード・マニング・カープ
（Richard Manning Karp）
- アメリカ / 1935年1月3日
- コンピュータ科学者
- カリフォルニア大学バークレー校 ユニバーシティ・プロフェッサー、国際コンピュータ科学研究所 上級研究員
計算複雑さの理論の発展への根幹的貢献
実用上重要なコンピュータ処理アルゴリズムを数多く開発するとともにＮＰ完全の理論を確立してアルゴリズムの評価や設計における指導原理に大きな影響を与え、1970年代初頭からの計算複雑さの理論の発展に根幹的な貢献をした。
略歴
- 1935年
- 米国マサチューセッツ州ボストン市生まれ
- 1959年
- ハーバード大学 博士号（応用数学）
- 1959年
- IBMトーマス・J・ワトソン研究センター 研究員
- 1968年
- カリフォルニア大学バークレー校 教授
- 1988年
- 国際コンピュータ科学研究所 研究員
- 1995年
- ワシントン大学 教授
- 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, 1971.
- 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.
- 1972年
Theoretical improvements in algorithmic efficiency for network flow problems (Edmonds, J. and Karp, R.). Journal of the ACM 19: 248-264, 1972.
- 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, 1979.
- 1985年
A fast parallel algorithm for the maximal independent set problem (with Wigderson, A.). Journal of the ACM 32: 762-773, 1985.
- 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, 2003.
計算複雑さの理論の発展への根幹的貢献
リチャード・マニング・カープ博士は、NP完全の理論を確立してアルゴリズムの評価や設計における指導原理に大きな影響を与え、1970年代初頭からの計算複雑さの理論の発展に根幹的な貢献をした。また、数多くの実用上重要なコンピュータ処理アルゴリズムを開発しアルゴリズム技術の発展に寄与した。
カープ博士は、組合せ問題の計算複雑さに関して、多項式時間還元の概念に基づいて同程度に難しい問題のクラスを定め、問題がどのクラスに属するかによって、問題の複雑さを計るという方法を創出して、NP完全の理論を確立した。これによりオペレーションズリサーチの最適化問題や計算機科学に関連する多くの身近な問題がNP完全なクラスに属する等しく難しい問題であることを示した。そして、そのための標準的な方法論を導き普及させ、計算機科学の根底を支える計算とアルゴリズムの理論を飛躍的に発展させた。
NP完全の理論は、「P対NP問題」と呼ばれる問題が現在でも計算機科学と数学の重要な未解決問題の一つになっていることにも象徴されるように、計算複雑さを科学の対象とすることを可能にし、人類の英知に新たなページを付け加えた。また、同理論はアルゴリズム工学の発展を促し、技術分野の多くの問題に対するアルゴリズムの評価や設計における指導原理に大きな影響を与え、アルゴリズム設計を個々の問題毎に対応するしかなかった手工業的状況から開放し、科学的技術へと変化させた。
この業績に加えて、カープ博士はエドモンズ-カープアルゴリズムの開発に代表されるように実用上重要なアルゴリズムを数多く開発するとともに、カープ博士が所属するカリフォルニア大学バークレー校を中心に理論計算機科学の拠点を築き、多くの若手研究者を育て、並列アルゴリズムや確率的アルゴリズムの理論の確立に指導的な役割を果した。最近の10年間では、計算機科学が他分野に役立つ研究、特に生命科学を助ける研究をすべきという信念から、バイオインフォマティクス分野におけるアルゴリズムの研究に大きな貢献をした。
以上の理由によって、リチャード・マニング・カープ博士に先端技術部門における第24回(2008)京都賞を贈呈する。
記念講演要旨
アルゴリズムのパワーと限界
両親の献身的な努力のおかげで、三人の弟妹と私は良い教育を受けさせてもらいました。数学との出会いは私にとって「初恋」のようなものでしたが、なかでもアルゴリズムには夢中になりました。アルゴリズムとは、計算問題を解くための段階的な手順のようなものです。皆さんが昔、学校で習った算数にもアルゴリズムが用いられています。
アルゴリズムは情報技術に関するありとあらゆるアプリケーションの基礎となっています。検索エンジンを使って欲しい情報が得られるのも、インターネットで特定のアドレスにメッセージが届くのもアルゴリズムのおかげです。また、電子商取引でも、データを暗号化して個人情報を保護するためにシンプルかつエレガントなアルゴリズムが使われています。
子供の頃、私は自分で考え出したアルゴリズムを使って、四桁の掛け算の暗算を友人達に披露していました。その後、父が数学を教えていた学校の時間割を管理するアルゴリズムを開発したりもしました。
良いアルゴリズムとは、正しい結果を効率的に導き出すものでなくてはなりません。アルゴリズムの効率とは、主として必要となる計算ステップの数で評価されます。私はネットワーク内の任意の目的地に情報を送る際の最大速度の計算や、大量のデータ内で繰り返されるパターンを探し出すことなど、実際的な問題を扱う効率的なアルゴリズムを開発してきました。しかし私の研究で最も知られているのは、ある種の問題が非常に難しいため、その解を求める効率的なアルゴリズムが存在しないことを証明する、というものでしょう。「NP完全」と呼ばれるこうした問題は、ほぼ全ての分野のアプリケーションで発生します。このNP完全という現象は、数多くの分野で働く人々に、例えば物理科学がそうであるように、ある計算に内在する複雑性を支配する基本的な限界がコンピュータ科学にも存在する、という認識を与えました。
私は、自分が最も心を惹かれたテーマを追求することが図らずも社会に役立つこととなり、この時代に生まれたことを感謝しています。また、私に生きる指針を与えてくれた両親にも感謝しています。そして、これまで研究という名の冒険を共にしてくれた数多くの学生、研究仲間、そして友人たちの友情とサポートは、私にとってかけがえもなく大切なものです。
- 【関連情報】
- 記念講演録（PDF）
ワークショップ
科学への計算世界観的アプローチ
Computational Approach to Science: Our Dream and Your Dream
- 日時
- 2008年11月12日（水）13：00～17：30
- 場所
- 国立京都国際会館
- 企 画
- 稲垣 康善 [豊橋技術科学大学 理事・副学長(先端技術部門 審査委員会 委員長)]
- 企画・司会
- 渡辺 治 [東京工業大学 大学院情報理工学研究科 教授]
- 主催
- 財団法人 稲盛財団
プログラム
