# Richard M. Karp ## 概要 Richard M. Karp（リチャード・カープ）は、カリフォルニア大学バークレー校（UC Berkeley）に所属した理論計算機科学者である。1972年の記念碑的論文『Reducibility Among Combinatorial Problems』において、Cook（1971）の充足可能性問題の完全性を足がかりに、グラフ彩色・クリーク・巡回セールスマン・整数計画法など広範な21の古典的組合せ最適化問題が互いに多項式時間で還元可能であること（Karpの21のNP完全問題）を示し、NP完全性理論を計算機科学全体の中核分野へと確立させた。1985年チューリング賞受賞。 ## 出典 - Richard M. Karp, "Reducibility Among Combinatorial Problems", *Complexity of Computer Computations*, pp. 85–103, Plenum Press, 1972.