卡普的二十一個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)
- 图着色问题(Chromatic number)
参见
參考資料
- ^ 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.