卡普的二十一個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）問題與弱完備（weakly complete）問題
ASR-complete
Ladner理論
NP困难
P/NP问题

參考資料

Stephen Cook. . . 1971: 151–158. 外部链接存在于|chapter= (帮助)
Richard M. Karp. . R. E. Miller and J. W. Thatcher (editors) (编). . New York: Plenum. 1972: 85–103.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Stephen Cook. . . 1971: 151–158. 外部链接存在于|chapter= (帮助)

[2] Richard M. Karp. . R. E. Miller and J. W. Thatcher (editors) (编). . New York: Plenum. 1972: 85–103.