卡普的二十一个NP-完全问题

计算复杂度理论内,一个极度重要的成就是史提芬·古克在1971年证明出了第一个NP-完全问题— 布尔可满足性问题[1]在1972年,理查德·卡普将这个想法往前推进,发表了他著名的论文"Reducibility Among Combinatorial Problems",其内证明了21个不同的,均因为其难解而恶名昭彰的组合数学图论问题,是NP-完全问题。[2]

借由展示出许多研究上面重要的问题是NP-完全问题,卡普促进了研究NP,NP-完备性,以及现在著名的P = NP这些问题。


问题

卡普的21个问题列表如下。下列问题加上了缩进排版,以表示出这些问题归约的方向。例如,精确覆盖问题可以归约到背包问题(Knapsack),因此背包问题是NP-完全问题。

参见

参考资料

  1. ^ Stephen Cook. The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. 1971: 151–158.  外部链接存在于|chapter= (帮助)
  2. ^ Richard M. Karp. Reducibility Among Combinatorial Problems. R. E. Miller and J. W. Thatcher (editors) (编). Complexity of Computer Computations. New York: Plenum. 1972: 85–103.