リチャード・カープ
1979年 - ファルカーソン賞
1985年 - チューリング賞
1990年 - ジョン・フォン・ノイマン理論賞
1994年 - Association for Computing Machinery フェロー
1996年 - アメリカ国家科学賞
1998年 - ハーヴェイ賞(イスラエル工科大学)
2004年 - ベンジャミン・フランクリン・メダル
2008年 - 京都賞先端技術部門、ディクソン賞科学部門(カーネギーメロン大学)
チューリング賞受賞理由は以下のとおり:
ネットワークフローや組合せ最適化問題に関する効率的アルゴリズムの開発、アルゴリズムの効率を判断する基準となる多項式時間の識別など計算理論に関する長年の貢献と、特にNP完全理論への貢献に対して。理論上でも実際上でも与えられた問題の計算複雑度を識別してNP完全かどうかを証明するための方法論はカープが導入し、今日では一般化している。
カープは情報工学とオペレーションズリサーチに関わる組合せ最適化について多数の重要な発見をしている。彼の最近の研究テーマにはバイオインフォマティクスも含まれる。
1971年、ジャック・エドモンズ(英語版)と共同でネットワークの最大フロー問題を解くエドモンズ-カープアルゴリズムを開発した。1972年、計算複雑性理論における重要な論文 "Reducibility Among Combinatorial Problems"(組合せ問題間の還元可能性)を発表し、その中で21の問題がNP完全であること(英語版)を証明した。
1973年、ジョン・ホップクロフトと共同でホップクロフト–カープのアルゴリズム(英語版)を発表。これは2部グラフの最大マッチングを求める最速の技法である。
1980年、リチャード・J・リプトン(英語版)と共にカープ-リプトンの定理(英語版)を証明した。この定理は、多項式個の論理ゲートを使ったブール回路(英語版)でSATが解けるなら、その多項式階層が第2レベルに折りたたまれることを証明したものである。
1987年、マイケル・ラビンと共同でラビン-カープ文字列探索アルゴリズムを開発した。