卡普的二十一个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）

参见

NP-complete问题列表
几乎完备（Almost complete（英语：Almost complete））问题与弱完备（weakly complete（英语：weakly complete））问题
ASR-complete
Ladner理论
NP困难
P/NP问题

参考资料

^ 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.

[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.

[1]

[2]