卡普的二十一个NP-完全问题
在计算复杂度理论内,一个极度重要的成就是史提芬·古克在1971年证明出了第一个NP-完全问题— 布尔可满足性问题。[1]在1972年,理查德·卡普将这个想法往前推进,发表了他著名的论文"Reducibility Among Combinatorial Problems",其内证明了21个不同的,均因为其难解而恶名昭彰的组合数学与图论问题,是NP-完全问题。[2]
借由展示出许多研究上面重要的问题是NP-完全问题,卡普促进了研究NP,NP-完备性,以及现在著名的P = NP这些问题。
问题
卡普的21个问题列表如下。下列问题加上了缩进排版,以表示出这些问题归约的方向。例如,精确覆盖问题可以归约到背包问题(Knapsack),因此背包问题是NP-完全问题。
- 布尔可满足性问题(Satisfiability):对于布尔逻辑内合取范式方程式的满足性问题(一般直接叫做SAT)
- 0-1整数规划(0-1 integer programming)
- 分团问题(Clique,参考独立集)
- Set packing(Set packing)
- 最小顶点覆盖问题(Vertex cover)
- 集合覆盖问题(Set covering)
- Feedback node set(Feedback node set)
- Feedback arc set
- 有向哈密顿循环(卡普命名,现称Directed Hamiltonian cycle)
- 无向哈密顿循环(卡普命名,现称Undirected Hamiltonian cycle)
- 每句话至多3个变量的布尔可满足性问题(Satisfiability with at most 3 literals per clause, 3-SAT)
参见
参考资料
- ^ Stephen Cook. The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. 1971: 151–158. 外部链接存在于
|chapter=
(帮助) - ^ 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.