卡普的二十一個NP-完全問題

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

問題[编辑]

卡普的21個問題列表如下,多數以問題的原名,加上巢狀排版表示出這些問題歸約的方向。舉例,背包問題(Knapsack)是NP-完全問題的證明,是從Exact cover歸約到背包問題,因此背包問題列為精确覆盖问题的子項。


參考資料[编辑]

  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//In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. 1972: 85–103.