卡普的二十一个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）
- 图着色问题（Chromatic number）
- 分团覆盖问题（Clique cover）
- 精确覆盖问题（Exact cover）
- Hitting set（Hitting set）
- Steiner tree（Steiner tree）
- 三维匹配问题（3-dimensional matching）
- 背包问题（Knapsack）
- Job sequencing（Job sequencing）
- 划分问题（Partition）
- 最大割问题（Max cut）
- 图着色问题（Chromatic number）
参见
[编辑]参考资料
[编辑]- ^ 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.