卡普的二十一個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
相關條目[编辑]
參考資料[编辑]
- ^ Stephen Cook. The Complexity of Theorem Proving Procedures//Proceedings of the third annual ACM symposium on Theory of computing. 1971: 151–158.
- ^ Richard M. Karp. Reducibility Among Combinatorial Problems//In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. 1972: 85–103.
