卡普的二十一个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 問題