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

一組計算問題 来自维基百科,自由的百科全书

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

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

問題

卡普的21個問題列表如下。下列問題加上了縮進排版,以表示出這些問題歸約的方向。例如,精確覆蓋問題可以歸約到背包問題(Knapsack),因此背包問題是NP-完全問題。

參見

參考資料

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.