Loading article…
リチャード・マニング・カープ（1935年1月3日生まれ）は、カリフォルニア大学バークレー校のアメリカ人コンピュータ科学者であり計算理論家である。彼はアルゴリズム理論の研究で最も有名であり、その功績により1985年にACMチューリング賞、2004年にベンジャミン・フランクリン・メダル（コンピュータおよび認知科学部門）、2008年に京都賞を受賞した。 [ 2 ]
カープは、NP完全性の理論と応用、効率的な組み合わせアルゴリズムの構築、およびコンピュータ科学における確率的手法の応用への多大な貢献により、1992年に米国工学アカデミーの会員に選出された。
マサチューセッツ州ボストンでアブラハムとローズ・カープ夫妻の間に生まれたカープには、ロバート、デビッド、キャロリンという3人の弟妹がいる。彼の家族はユダヤ人で[ 3 ] 、当時ユダヤ人が大多数を占めていたボストンのドーチェスター地区の小さなアパートで育った。
両親ともにハーバード大学の卒業生で（母親は夜間コースを受講して57歳でハーバード大学の学位を取得）、父親はハーバード大学卒業後に医学部進学を目指していたが、医学部の学費を払えなかったため数学教師になった。[ 3 ]彼はハーバード大学に入学し、1955年に学士号、1956年に修士号、 1959年に応用数学の博士号を取得した。IBMのトーマス・J・ワトソン研究所で働き始めた。
1968年、カープはカリフォルニア大学バークレー校のコンピュータ科学、数学、オペレーションズリサーチの教授に就任した。カープは電気工学・コンピュータ科学科内のコンピュータ科学部門の初代副主任を務めた。[ 4 ]ワシントン大学で4年間教授を務めた期間を除き、彼はバークレーに留まっている。1988年から1995年、そして1999年から現在まで、彼はバークレーの国際コンピュータ科学研究所の研究員も務めており、現在はアルゴリズムグループを率いている。
リチャード・カープは、計算複雑性に関する洞察により、国家科学勲章を授与され、テクニオンのハーベイ賞 と2004年のベンジャミン・フランクリン・メダル（コンピュータおよび認知科学部門）を受賞しました。1994年には、Association for Computing Machineryのフェローに選出されました。2002年には、Institute for Operations Research and the Management Sciencesのフェローに選出されました。[ 5 ]彼は、いくつかの名誉学位を授与されており、米国科学アカデミー[ 6 ]、アメリカ芸術科学アカデミー[ 7 ]、およびアメリカ哲学協会[ 8 ]の会員です。
2012年、カープはカリフォルニア大学バークレー校のサイモンズ理論計算機科学研究所の創設所長に就任した。[ 9 ]
カープは、コンピュータ科学、組み合わせアルゴリズム、オペレーションズリサーチの分野で数々の重要な発見を成し遂げてきた。彼の現在の主な研究テーマはバイオインフォマティクスである。
1962年、彼はマイケル・ヘルドと共同で、巡回セールスマン問題に対する正確な指数時間アルゴリズムであるヘルド・カープアルゴリズムを開発した。
1971年、彼はジャック・エドモンズと共同でネットワーク上の最大フロー問題を解くためのエドモンズ・カープアルゴリズムを開発し、1972年には複雑性理論における画期的な論文「組み合わせ問題間の還元可能性」を発表し、その中で21の問題がNP完全であることを証明した。[ 10 ]
1973年、彼はジョン・ホプクロフトと共に、二部グラフにおける最大カーディナリティのマッチングを見つけるための最速の既知の方法であるホプクロフト・カープアルゴリズムを発表した。
1980年、カープはリチャード・J・リプトンと共にカープ・リプトンの定理を証明した（ SATが多項式数の論理ゲートを持つブール回路で解ける場合、多項式階層は第2レベルに縮退するという定理）。
1987年、彼はマイケル・O・ラビンと共にラビン・カープ文字列検索アルゴリズムを共同開発した。
彼が（1985年の）チューリング賞を受賞した際の表彰状[ 11 ]は以下の通りである。
アルゴリズム理論への継続的な貢献、特にネットワークフローやその他の組み合わせ最適化問題に対する効率的なアルゴリズムの開発、多項式時間計算可能性とアルゴリズム効率の直感的な概念との関連付け、そして最も注目すべきはNP完全性理論への貢献に対して、カープは、問題がNP完全であることを証明するための現在では標準的な方法論を導入し、これにより多くの理論的および実践的な問題が計算上困難であることが明らかになった。