卡普的二十一個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問題

參考資料

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.