リチャード・カープとは？
りちゃーどかーぷ
リチャード・カープは、NP完全問題の理論を確立し計算複雑性理論に革命をもたらしたアメリカの計算機科学者です。
リチャード・カープ（1935年〜）は、アメリカ・ボストン生まれの計算機科学者で、アルゴリズム理論と計算複雑性理論の発展に多大な貢献をした研究者です。ハーバード大学で数学の博士号を取得し、現在はカリフォルニア大学バークレー校の教授を務めています。
カープの最も著名な業績は、1972年に発表した論文「Reducibility Among Combinatorial Problems」です。この論文でカープは、スティーブン・クックが提唱したNP完全性の概念を応用し、グラフ理論・整数計画法・論理など多様な分野から21個の問題を取り上げ、それらがすべてNP完全であることを多項式時間還元（帰着）によって証明しました。
この業績により「カープの21問題」という言葉が生まれ、計算複雑性理論における「解くのが難しい問題の体系的な分類」という研究方向が確立されました。P≠NP問題（効率的に解けるか否か）はいまも未解決の重要問題であり、カープの研究はその中心に位置しています。
また、カープはアルゴリズム設計においても多くの貢献をしており、ラビン-カープ文字列探索アルゴリズム（ハッシュを利用した高速文字列照合）はその代表例です。これらの功績により、1985年にはチューリング賞を受賞しています。
使い方・例文
情報科学の計算複雑性理論の授業では、充足可能性問題（SAT）や巡回セールスマン問題がNP完全であることを示す文脈でカープの論文が必ず参照されます。
この用語をシェア
最終更新: