https://wiki.taigi.ima.org.tw/w/index.php?action=history&feed=atom&title=%E5%8D%A1%E6%99%AE%E7%9A%84%E4%BA%8C%E5%8D%81%E4%B8%80%E4%B8%AANP-%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C 2026-05-09T19:15:04Z 本 wiki 上此頁面的修訂紀錄 MediaWiki 1.43.1 https://wiki.taigi.ima.org.tw/w/index.php?title=%E5%8D%A1%E6%99%AE%E7%9A%84%E4%BA%8C%E5%8D%81%E4%B8%80%E4%B8%AANP-%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C&diff=465147&oldid=prev 2025-08-23T07:22:25Z

<p>從 JSON 檔案批量匯入</p> <p><b>新頁面</b></p><div>佇咧算複雜度理論內，一个極度重要的成就是史提芬 ・ 古克佇一九七一年證明出了頭一个 NP-完全問題—布而已會當滿足的問題。佇一九七二年，理察 ・ 卡普將這个想法向前捒入去，發表了伊出名的論文 &quot;&#039;&#039;&#039;Reducibility Among Combinatorial Problems&#039;&#039;&#039;&quot;，其內證明二十一个無仝的，均因為其歹解倒落名聲昭彰的組合數學佮圖論問題，是 NP-完全問題。<br /> <br /> 透過展示出濟濟研究頂面重要的問題是 NP-完全問題，卡普促進了研究 NP，NP-完備性，以及這馬出名的 P=NP 遮的問題。<br /> <br /> <br /> <br /> ==問題==<br /> <br /> 卡普的二十一个問題列表如下。下列問題加上矣縮入去排版，以表示出遮的問題歸約的方向。比如講，精確覆蓋問題會當歸約到背包問題（Knapsack）， 所以揹仔問題是 NP-完全問題。<br /> <br /> * 布而已會當滿足的問題（Satisfiability）： 對布爾邏輯內合取範式方程式滿足性問題（一般直接叫做 SAT）<br /> * 零劃一整數規劃（空七一 integer programming）<br /> * 分團問題（Clique，參考獨立集）<br /> * Set packing（Set packing）<br /> * 上細頂點崁問題（Vertex cover）<br /> * 集合崁問題（Set covering）<br /> * Feedback node set（Feedback node set）<br /> * Feedback arc set<br /> * 有共哈密頓迴箍（卡普號名，現稱 Directed Hamiltonian cycle）<br /> * 無向哈密頓迴箍（卡普號名，現稱 Undirected Hamiltonian cycle）<br /> * 逐句話至濟三个變量的布爾會當滿足來問題（Satisfiability with at most 三 literals per clause , 三-SAT）<br /> * 圖上色的問題（Chromatic number）<br /> * 分團崁問題（Clique cover）<br /> * 精確覆起問題（Exact cover）<br /> * Hitting set（Hitting set）<br /> * Steiner tree（Steiner tree）<br /> * 三維匹配的問題（三-dimensional matching）<br /> * 揹仔問題（Knapsack）<br /> * Job sequencing（Job sequencing）<br /> * 劃分問題（Partition）<br /> * 最大割問題（Max cut）<br /> <br /> ==參見==<br /> <br /> * NP-complete 問題列表<br /> * 差不多完備（Almost complete）問題佮弱完備（weakly complete）問題<br /> * ASR-complete<br /> * Ladner 理論<br /> * NP 困難喔<br /> * P / NP 問題<br /> <br /> ==參考資料==<br /> <br /> [[分類: 待校正]]</div>

TaiwanTonguesApiRobot