リチャード・マニング・カープ（Richard Manning Karp、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。
| リチャード・マニング・カープ | |
|---|---|
| EPFLにて（2009年7月） | |
| 生誕 | 1935年1月3日（88歳） マサチューセッツ州ボストン |
| 国籍 | アメリカ合衆国 |
| 研究分野 | 計算機科学 |
| 研究機関 | カリフォルニア大学バークレー校 IBM |
| 出身校 | ハーバード大学 |
| 博士課程 指導教員 | Anthony Oettinger[1] |
| 博士課程 指導学生 | ナレンドラ・カーマーカー |
| 主な業績 | エドモンズ・カープのアルゴリズム (カープの21のNP完全問題) (ホップクロフト–カープのアルゴリズム) (カープ–リプトンの定理) ラビン-カープ文字列検索アルゴリズム |
| 主な受賞歴 | チューリング賞(1985) ジョン・フォン・ノイマン理論賞(1990) アメリカ国家科学賞(1996) ベンジャミン・フランクリン・メダル(2004) |
| プロジェクト:人物伝 | |
経歴
ボストン生まれ。弟妹が3人いる。ハーバード大学で1955年に学士号、1956年に修士号、1959年に応用数学の博士号を取得した。
その後、IBMのトーマス・J・ワトソン研究所に勤務。1968年、カリフォルニア大学バークレー校の計算機科学、数学、オペレーションズリサーチに関する教授となった。4年間だけワシントン大学で教授を務めたが、それ以外は常にバークレーにとどまっていた。1988年から1995年までと、1995年以降、バークレーの(国際計算機科学研究所)の研究員も務め、2012年現在は同研究所のアルゴリズム部門を指揮している。
業績
カープは情報工学とオペレーションズリサーチに関わる組合せ最適化について多数の重要な発見をしている。彼の最近の研究テーマにはバイオインフォマティクスも含まれる。
1971年、(ジャック・エドモンズ)と共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。1972年、計算複雑性理論における重要な論文 "Reducibility Among Combinatorial Problems"（組合せ問題間の還元可能性）を発表し、その中で(21の問題がNP完全であること)を証明した[2]。
1973年、ジョン・ホップクロフトと共同で(ホップクロフト–カープのアルゴリズム)を発表。これは2部グラフの最大マッチングを求める最速の技法である。
1980年、(リチャード・J・リプトン)と共に(カープ-リプトンの定理)を証明した。この定理は、多項式個の論理ゲートを使った(ブール回路)でSATが解けるなら、その多項式階層が第2レベルに折りたたまれることを証明したものである。
1987年、マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。
主な受賞歴
- 1979年 - ファルカーソン賞
- 1985年 - チューリング賞
- 1990年 - ジョン・フォン・ノイマン理論賞
- 1994年 - Association for Computing Machinery フェロー
- 1996年 - アメリカ国家科学賞
- 1998年 - ハーヴェイ賞（イスラエル工科大学）
- 2004年 - ベンジャミン・フランクリン・メダル
- 2008年 - 京都賞先端技術部門[3]、ディクソン賞科学部門（カーネギーメロン大学）
チューリング賞受賞理由は以下のとおり:
- ネットワークフローや組合せ最適化問題に関する効率的アルゴリズムの開発、アルゴリズムの効率を判断する基準となる多項式時間の識別など計算理論に関する長年の貢献と、特にNP完全理論への貢献に対して。理論上でも実際上でも与えられた問題の計算複雑度を識別してNP完全かどうかを証明するための方法論はカープが導入し、今日では一般化している。
脚注
- ^ リチャード・カープ - Mathematics Genealogy Project
- ^ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103
- ^ Richard Manning Karp Inamori Foundation
外部リンク
- カリフォルニア大学バークレー校のホームページ
- ACM Crossroads magazine interview/bio of Richard Karp