卡普的二十一个NP-完全问题一組計算問題 / 维基百科,自由的 encyclopedia 在计算复杂度理论内,一个极度重要的成就是史提芬·古克在1971年证明出了第一个NP-完全问题— 布尔可满足性问题。[1]在1972年,理查德·卡普将这个想法往前推进,发表了他著名的论文"Reducibility Among Combinatorial Problems",其内证明了21个不同的,均因为其难解而恶名昭彰的组合数学与图论问题,是NP-完全问题。[2] 借由展示出许多研究上面重要的问题是NP-完全问题,卡普促进了研究NP,NP-完备性,以及现在著名的P = NP这些问题。
在计算复杂度理论内,一个极度重要的成就是史提芬·古克在1971年证明出了第一个NP-完全问题— 布尔可满足性问题。[1]在1972年,理查德·卡普将这个想法往前推进,发表了他著名的论文"Reducibility Among Combinatorial Problems",其内证明了21个不同的,均因为其难解而恶名昭彰的组合数学与图论问题,是NP-完全问题。[2] 借由展示出许多研究上面重要的问题是NP-完全问题,卡普促进了研究NP,NP-完备性,以及现在著名的P = NP这些问题。