1985年理察·卡普 Richard Manning Karp 在Steven Cook提出NP-Complete並 證明SAT是NP-Complete之後，Richard 理察卡普2009年7月於洛柔聯邦理工學院 Karp證明了21個問題都是NP 出生 1935年1月3日 波士頓，麻罐諸塞州·美國 研究箱域計算機科學 Complete。 任联於 柏克禁加州大學 IBM .0-1 integer programming Chromatic number 母校 哈佛大學 。Clique 。Clique cover 博士尊師Anthony Oettinger 。Set packing Exact cover 傅士學生Narendra Karmarkar Vertex cover ·Hitting set Michael Luby Steiner tree 。Set covering Rajeev Motwani 3-dimensional matching Barbara Simons Feedback node set ·Knapsack Feedback arc set 著名成就Edmonds-Karp algorithm 。Job sequencing Karp's 21 NP-complete problems Directed Hamilton circuit Partition Hopcroft Karp算法 Undirected Hamilton circuit Karp-Lipton theorem 。Max cut Rabin-Karp string search algorithm1985 年 理察 · 卡普 Richard Manning Karp ● 在 Steven Cook 提出 NP-Complete 並 證明 SAT 是 NP-Complete 之後， Richard Karp 證明了 21 個問題都是 NP￾Complete