檢視卡普的二十一个NP-完全問題的原始碼

佇咧算複雜度理論內，一个極度重要的成就是史提芬 ・ 古克佇一九七一年證明出了頭一个 NP-完全問題—布而已會當滿足的問題。佇一九七二年，理察 ・ 卡普將這个想法向前捒入去，發表了伊出名的論文 "'''Reducibility Among Combinatorial Problems'''"，其內證明二十一个無仝的，均因為其歹解倒落名聲昭彰的組合數學佮圖論問題，是 NP-完全問題。

透過展示出濟濟研究頂面重要的問題是 NP-完全問題，卡普促進了研究 NP，NP-完備性，以及這馬出名的 P=NP 遮的問題。



==問題==

卡普的二十一个問題列表如下。下列問題加上矣縮入去排版，以表示出遮的問題歸約的方向。比如講，精確覆蓋問題會當歸約到背包問題（Knapsack）， 所以揹仔問題是 NP-完全問題。

* 布而已會當滿足的問題（Satisfiability）： 對布爾邏輯內合取範式方程式滿足性問題（一般直接叫做 SAT）
* 零劃一整數規劃（空七一 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）
* 逐句話至濟三个變量的布爾會當滿足來問題（Satisfiability with at most 三 literals per clause , 三-SAT）
* 圖上色的問題（Chromatic number）
* 分團崁問題（Clique cover）
* 精確覆起問題（Exact cover）
* Hitting set（Hitting set）
* Steiner tree（Steiner tree）
* 三維匹配的問題（三-dimensional matching）
* 揹仔問題（Knapsack）
* Job sequencing（Job sequencing）
* 劃分問題（Partition）
* 最大割問題（Max cut）

==參見==

* NP-complete 問題列表
* 差不多完備（Almost complete）問題佮弱完備（weakly complete）問題
* ASR-complete
* Ladner 理論
* NP 困難喔
* P / NP 問題

==參考資料==

[[分類: 待校正]]