リチャード・カープ

リチャード・マニング・カープ（"Richard Manning Karp"、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。
経歴.
ボストン生まれ。弟妹が3人いる。ハーバード大学で1955年に学士号、1956年に修士号、1959年に応用数学の博士号を取得した。
その後、IBMのトーマス・J・ワトソン研究所に勤務。1968年、カリフォルニア大学バークレー校の計算機科学、数学、オペレーションズリサーチに関する教授となった。4年間だけワシントン大学で教授を務めたが、それ以外は常にバークレーにとどまっていた。1988年から1995年までと、1995年以降、バークレーのの研究員も務め、2012年現在は同研究所のアルゴリズム部門を指揮している。
業績.
カープは情報工学とオペレーションズリサーチに関わる組合せ最適化について多数の重要な発見をしている。彼の最近の研究テーマにはバイオインフォマティクスも含まれる。
1971年、と共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。1972年、計算複雑性理論における重要な論文 "Reducibility Among Combinatorial Problems"（組合せ問題間の還元可能性）を発表し、その中でを証明した。
1973年、ジョン・ホップクロフトと共同でを発表。これは2部グラフの最大マッチングを求める最速の技法である。
1980年、と共にを証明した。この定理は、多項式個の論理ゲートを使ったでSATが解けるなら、その多項式階層が第2レベルに折りたたまれることを証明したものである。
1987年、マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。
主な受賞歴.
チューリング賞受賞理由は以下のとおり:
外部リンク.