Definición y significado de 卡普的二十一個NP-完全問題

在計算複雜度理論內，一個極度重要的成就是史提芬·古克在 1971證明出了第一個NP-完全 problem問題 — 布爾可滿足性問題。^[1]在1972年，理查德·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。^[2]

藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。

  問題

卡普的21個問題列表如下，多數以問題的原名，加上巢狀排版表示出這些問題歸約的方向。舉例，背包問題（KNAPSACK）是NP-完全問題的證明，是從EXACT COVER問題歸約到KNAPSACK，因此KNAPSACK列為EXACT COVER的子項。

• 布爾可滿足性問題（SATISFIABILITY）：對於布爾邏輯內合取範式方程式的滿足性問題（一般直接叫做SAT）
  • 0-1 整數規劃（0-1 INTEGER PROGRAMMING）
  • 分團問題（CLIQUE）（參考獨立集）
    • SET PACKING
    • VERTEX COVER(VERTEX COVER)
      • SET COVERING(SET COVERING)
      • FEEDBACK NODE SET(FEEDBACK NODE SET)
      • FEEDBACK ARC SET
      • 有向哈密頓迴圈 (卡普命名為DIRECTED HAMILTON CIRCUIT，現在一般命名為DIRECTED HAMILTONIAN CIRCUIT)
        • 無向哈密頓迴圈 (卡普命名為UNDIRECTED HAMILTON CIRCUIT，現在一般命名為UNDIRECTED HAMILTONIAN CIRCUIT)
  • SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE (equivalent to 3-SAT)
    • CHROMATIC NUMBER
      • 分團覆蓋問題（CLIQUE COVER）
      • 精確覆蓋問題（EXACT COVER）
        • HITTING SET
        • STEINER TREE
        • 3-DIMENSIONAL MATCHING
        • 背包問題（KNAPSACK）
          • JOB SEQUENCING
          • PARTITION
            • MAX CUT

  相關條目

• NP-完全問題列表

  參考資料

1. ^ Stephen Cook. The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. 1971:  151–158. 
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.