リチャード・カープ

リチャード・マニング・カープ（Richard Manning Karp、1935年 - ）は、情報工学者にして計算理論家であり、計算理論の研究で知られている。1985年にチューリング賞を受賞した。また、2008年には京都賞を受賞した。

カープはボストンに生まれた。ハーバード大学で1955年に学士号、1956年に修士号、1959年に応用数学の博士号を取得した。その後、IBMのトーマス・J・ワトソン研究所に勤務した。1968年、カリフォルニア大学バークレー校の情報工学、数学、オペレーションズリサーチに関する教授となった。4年間だけワシントン大学で教授を務めたが、それ以外は常にバークレーにとどまっていた。2004年、カープは計算複雑性理論への貢献に対してベンジャミン・フランクリンメダルを授与された。

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

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

1971年、彼はジャック・エドモンズと共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。 1987年、彼はマイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを共同開発した。

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