リチャード・カープ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
リチャード・マニング・カープ
EPFLにて(2009年7月)
人物情報
生誕 1935年1月3日(79歳)
マサチューセッツ州ボストン
国籍 アメリカ合衆国の旗 アメリカ合衆国
出身校 ハーバード大学
学問
研究分野 計算機科学
研究機関 カリフォルニア大学バークレー校
IBM
博士課程
指導教員
Anthony Oettinger[1]
博士課程
指導学生
ナレンドラ・カーマーカー
主な業績 エドモンズ・カープのアルゴリズム
カープの21のNP完全問題英語版
ホップクロフト–カープのアルゴリズム英語版
カープ–リプトンの定理英語版
ラビン-カープ文字列検索アルゴリズム
主な受賞歴 チューリング賞
アメリカ国家科学賞
京都賞
テンプレートを表示

リチャード・マニング・カープRichard Manning Karp1935年1月3日 - )は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍し、1985年にチューリング賞、2004年にベンジャミン・フランクリン・メダル、2008年に京都賞を受賞[2]

経歴[編集]

ボストン生まれ。弟妹が3人いる。ハーバード大学1955年に学士号、1956年に修士号、1959年応用数学の博士号を取得した。

その後、IBMトーマス・J・ワトソン研究所に勤務。1968年カリフォルニア大学バークレー校の計算機科学、数学、オペレーションズリサーチに関する教授となった。4年間だけワシントン大学で教授を務めたが、それ以外は常にバークレーにとどまっていた。1988年から1995年までと、1995年以降、バークレーの国際計算機科学研究所英語版の研究員も務め、2012年現在は同研究所のアルゴリズム部門を指揮している。

業績[編集]

カープは情報工学とオペレーションズリサーチに関わる組合せ最適化について多数の重要な発見をしている。彼の最近の研究テーマにはバイオインフォマティクスも含まれる。

1971年ジャック・エドモンズ英語版と共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。1972年、計算複雑性理論における重要な論文 "Reducibility Among Combinatorial Problems"(組合せ問題間の還元可能性)を発表し、その中で21の問題がNP完全であること英語版を証明した[3]

1973年、ジョン・ホップクロフトと共同でホップクロフト–カープのアルゴリズム英語版を発表。これは2部グラフの最大マッチングを求める最速の技法である。

1980年、リチャード・J・リプトン英語版と共にカープ-リプトンの定理英語版を証明した。この定理は、多項式個の論理ゲートを使ったブール回路英語版SATが解けるなら、その多項式階層が第2レベルに折りたたまれることを証明したものである。

1987年マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。

主な受賞歴[編集]

チューリング賞受賞理由は以下のとおり:

ネットワークフローや組合せ最適化問題に関する効率的アルゴリズムの開発、アルゴリズムの効率を判断する基準となる多項式時間の識別など計算理論に関する長年の貢献と、特にNP完全理論への貢献に対して。理論上でも実際上でも与えられた問題の計算複雑度を識別してNP完全かどうかを証明するための方法論はカープが導入し、今日では一般化している。

脚注[編集]

  1. ^ リチャード・カープ - Mathematics Genealogy Project
  2. ^ Richard Manning Karp Inamori Foundation
  3. ^ 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. http://www.cs.berkeley.edu/~luca/cs172/karp.pdf. 

外部リンク[編集]