リチャード・M・カープ

リチャード・マニング・カープ
2009年、EPFLのリチャード・カープ
生まれる	( 1935-01-03 )1935年1月3日（89歳） ボストン、マサチューセッツ州、米国
国籍	アメリカ人
母校	ハーバード大学( BA、MA、PhD )
知られている	アンデラー・カープ・ローゼンバーグ予想 エドモンズ・カープアルゴリズム ヘルド・カープアルゴリズム ホップクロフト・カープアルゴリズム カーマーカー・カープアルゴリズム ラビン・カープ文字列検索アルゴリズム カープ・リプトンの定理 カープの21のNP完全問題 ベクトル加算システム
受賞歴	ファルカーソン賞 (1979) チューリング賞 (1985) ジョン・フォン・ノイマン理論賞 (1990) IEEEコンピュータ協会チャールズ・バベッジ賞 (1995) アメリカ国家科学賞 (1996) ハーヴェイ賞 (1998) EATCS賞 (2000) ベンジャミン・フランクリン賞 (2004) 京都賞 (2008)
科学者としてのキャリア
フィールド	コンピュータサイエンス
機関	カリフォルニア大学バークレー校 IBM
論文	論理構文のデジタルコンピュータプログラミングへの応用 (1959)
博士課程の指導教員	アンソニー・エッティンガー[1]
博士課程の学生	フェイス・エレン サリー・フロイド フィリップ・ギボンズ ダン・ガスフィールド ナレンドラ・カルマルカル ヴァレリー・キング マイケル・ルビー ラジーヴ・モトワニ ノアム・ニサン レイモンド・ライター ユーニス・サントス トーマス・J・シェーファー ロン・シャミア バーバラ・シモンズ エリック・シン ノーマン・ザデー[1]

リチャード・マニング・カープ（1935年1月3日生まれ）は、アメリカのコンピュータ科学者、カリフォルニア大学バークレー校の計算理論家である。彼はアルゴリズム理論の研究で最も有名で、 1985年にチューリング賞、 2004年にコンピュータと認知科学におけるベンジャミン・フランクリン賞、2008年に京都賞を受賞した。 ^[2]

カープは、NP完全性の理論と応用、効率的な組み合わせアルゴリズムの構築、コンピュータサイエンスにおける確率的手法の応用に対する多大な貢献により、 米国工学アカデミーの会員に選出されました（1992年）。

マサチューセッツ州ボストンでアブラハムとローズ・カープの両親のもとに生まれたカープには、ロバート、デイビッド、キャロリンの3人の弟妹がいる。彼の家族はユダヤ人であり、^{[3]彼はボストンの}ドーチェスターの当時はユダヤ人がほとんど住んでいた地区の小さなアパートで育った。

両親はともにハーバード大学の卒業生（母親は夜間コースを受講し、57歳でハーバード大学の学位を取得した）である一方、父親はハーバード大学卒業後に医学部への進学を希望していたが、学費を払うことができず数学の教師になった。^[3]彼はハーバード大学に入学し、1955年に学士号、1956年に修士号、 1959年に応用数学の博士号を取得した。彼はIBMのトーマス・J・ワトソン研究所で働き始めた。

1968年、彼はカリフォルニア大学バークレー校でコンピュータサイエンス、数学、オペレーションズリサーチの教授に就任した。カープは電気工学およびコンピュータサイエンス学部内のコンピュータサイエンス部門の初代副学部長であった。^[4]ワシントン大学で教授を務めた4年間を除いて、彼はバークレーに留まった。1988年から1995年と1999年から現在まで、彼はバークレーの国際コンピュータサイエンス研究所の研究科学者でもあり、現在はアルゴリズムグループを率いている。

リチャード・カープは、計算複雑性に関する洞察により、アメリカ国家科学賞を受賞し、テクニオンのハーヴェイ賞 と2004年のベンジャミン・フランクリン・メダルをコンピュータと認知科学で受賞した。1994年に、彼は計算機協会のフェローに就任した。彼は、2002年にオペレーションズ・リサーチおよび経営科学研究所のフェローに選出された。^[5]彼は、いくつかの名誉学位を授与されており、米国科学アカデミー^[6]、アメリカ芸術科学アカデミー^[7]、アメリカ哲学協会の会員である。^[8]

2012年、カープはカリフォルニア大学バークレー校のシモンズ計算理論研究所の初代所長に就任した。^[9]

カープ氏は、コンピュータサイエンス、組み合わせアルゴリズム、オペレーションズリサーチの分野で多くの重要な発見をしてきました。彼の現在の主な研究対象はバイオインフォマティクスです。

1962年に彼はマイケル・ヘルドと共同で、巡回セールスマン問題に対する正確な指数時間アルゴリズムであるヘルド・カープアルゴリズムを開発しました。

1971年にジャック・エドモンズと共同で、ネットワーク上の最大フロー問題を解くエドモンズ・カープアルゴリズムを開発し、1972年には複雑性理論における画期的な論文「組合せ問題の中の還元可能性」を発表し、その中で21の問題がNP完全であることを証明した。^[10]

1973年に彼とジョン・ホップクロフトは、二部グラフで最大濃度マッチングを見つけるための最も高速な方法であるホップクロフト・カープアルゴリズムを発表しました。

1980年、カープはリチャード・J・リプトンとともにカープ・リプトンの定理（多項式個の論理ゲートを持つブール回路でSATを解くことができる場合、多項式階層は第2レベルに崩壊することを証明する）を証明した。

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

1985年のチューリング賞受賞理由^[11]は次の通りである。

ネットワークフローやその他の組み合わせ最適化問題に対する効率的なアルゴリズムの開発、アルゴリズムの効率性の直感的な概念による多項式時間計算可能性の特定、そして最も顕著なNP完全性理論への貢献など、アルゴリズム理論への継続的な貢献に対して。カープは、問題がNP完全であることを証明するための現在では標準的な方法論を導入し、これにより多くの理論的および実際的な問題が計算上困難であると特定されるようになりました。

ウィキメディア・コモンズには、リチャード・カープに関連するメディアがあります。

• ACM クロスロード誌のリチャード・カープのインタビュー/経歴
• バークレーのカープのホームページ
• オペレーションズ・リサーチおよび経営科学研究所のリチャード・カープの経歴