検索
Richard Manning Karp
第24回(2008)受賞
情報科学
/ コンピュータ科学者
1935 -
カリフォルニア大学バークレー校 ユニバーシティ・プロフェッサー、国際コンピュータ科学研究所 上級研究員
実用上重要なコンピュータ処理アルゴリズムを数多く開発するとともにＮＰ完全の理論を確立してアルゴリズムの評価や設計における指導原理に大きな影響を与え、1970年代初頭からの計算複雑さの理論の発展に根幹的な貢献をした。
リチャード・マニング・カープ博士は、NP完全の理論を確立してアルゴリズムの評価や設計における指導原理に大きな影響を与え、1970年代初頭からの計算複雑さの理論の発展に根幹的な貢献をした。また、数多くの実用上重要なコンピュータ処理アルゴリズムを開発しアルゴリズム技術の発展に寄与した。
カープ博士は、組合せ問題の計算複雑さに関して、多項式時間還元の概念に基づいて同程度に難しい問題のクラスを定め、問題がどのクラスに属するかによって、問題の複雑さを計るという方法を創出して、NP完全の理論を確立した。これによりオペレーションズリサーチの最適化問題や計算機科学に関連する多くの身近な問題がNP完全なクラスに属する等しく難しい問題であることを示した。そして、そのための標準的な方法論を導き普及させ、計算機科学の根底を支える計算とアルゴリズムの理論を飛躍的に発展させた。
NP完全の理論は、「P対NP問題」と呼ばれる問題が現在でも計算機科学と数学の重要な未解決問題の一つになっていることにも象徴されるように、計算複雑さを科学の対象とすることを可能にし、人類の英知に新たなページを付け加えた。また、同理論はアルゴリズム工学の発展を促し、技術分野の多くの問題に対するアルゴリズムの評価や設計における指導原理に大きな影響を与え、アルゴリズム設計を個々の問題毎に対応するしかなかった手工業的状況から開放し、科学的技術へと変化させた。
この業績に加えて、カープ博士はエドモンズ-カープアルゴリズムの開発に代表されるように実用上重要なアルゴリズムを数多く開発するとともに、カープ博士が所属するカリフォルニア大学バークレー校を中心に理論計算機科学の拠点を築き、多くの若手研究者を育て、並列アルゴリズムや確率的アルゴリズムの理論の確立に指導的な役割を果した。最近の10年間では、計算機科学が他分野に役立つ研究、特に生命科学を助ける研究をすべきという信念から、バイオインフォマティクス分野におけるアルゴリズムの研究に大きな貢献をした。
以上の理由によって、リチャード・マニング・カープ博士に先端技術部門における第24回(2008)京都賞を贈呈する。
プロフィールは受賞時のものです