カープ, リチャード・M

【かーぷ, りちゃーど・M (Karp, Richard M.)】

カープは, 問題の計算量の概念と効率的アルゴリズムの研究の先駆者であり, 今日の情報科学の基盤を確立した. 特に, NP完全問題の系統的分類, 巡回セールスマン問題に対する解法, ネットワークフローや2部グラフの最大マッチングの高速アルゴリズムなどの業績は有名で, ランチェスター賞(1977), ファルカーソン賞(1979), ACMチューリング賞(1985), フォンノイマン賞(1990)を受賞している(1935-　).