|
リチャード・カープ
リチャード・マニング・カープ（Richard Manning Karp、1935年1月3日 - ）は、計算機科学者にして計算理論家であり、計算理論の研究で知られている。カリフォルニア大学バークレー校に在籍。 経歴ボストン生まれ。弟妹が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年、マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。 主な受賞歴
チューリング賞受賞理由は以下のとおり:
脚注
外部リンクInformation related to リチャード・カープ |
||||||||||||||||||||||||
