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