カープとは？
かーぷ
リチャード・マニング・カープは、アルゴリズム理論と計算複雑性理論に多大な貢献をしたアメリカの計算機科学者です。
リチャード・マニング・カープ（Richard Manning Karp、1935年生まれ）は、アメリカの計算機科学者・数学者で、アルゴリズム設計と計算複雑性理論の分野で20世紀後半を代表する業績を残しました。
カープが特に広く知られているのは、1972年に発表した論文「Reducibility Among Combinatorial Problems」です。この論文では、グラフ彩色問題・ハミルトン閉路問題・整数計画問題など21種類の組合せ最適化問題がいずれもNP完全であることを一挙に証明し、計算困難性の研究に決定的な基盤を与えました。
また、ホップクロフトとともに二部グラフの最大マッチングを効率的に求めるホップクロフト・カープ・アルゴリズムを開発したほか、カープ・ラビン文字列検索アルゴリズム（ローリングハッシュを用いた高速な部分文字列探索法）も共同考案しています。
計算複雑性理論・グラフ理論・乱択アルゴリズムにわたる貢献が評価され、1985年にチューリング賞を受賞しました。現在もカリフォルニア大学バークレー校の教授として理論計算機科学の研究を続けています。
使い方・例文
アルゴリズムの教科書で「NP完全問題」を説明する際、カープが示した21問題の帰着証明が基礎的な参考文献として登場します。
この用語をシェア
最終更新: