推 wayne750213:都GG了~~你還留在這裡惹人嫌嗎 06/28 00:00
推 cair:我PO文的時間 是我開始看的時間=3= 06/28 00:37
http://zh.wikipedia.org/w/index.php?title=NP%E5%AE%8C%E5%85%A8&variant=zh-tw
在計算複雜度理論的世界中，NPC問題是NP（非決定性多項式時間）中最難的決定性問題
。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合
。許多人推測P與NPC沒有交集。理由是因若任何NPC問題得到多項式時間的解法，那此解
法就可應用在所有NP問題上。
一個決定性問題C若是為NPC，則代表它對NP是完備的，這表示:
它是一個NP問題，且
它是一個NP-困難問題，意即其他屬於NP的問題可變換（reducible）成它。
可變換在此意指對每個問題L，總有一個多項式時間多對一變換，即一個決定性的演算法
可以將實例l ∈ L 轉化成實例c ∈ C，並讓c 回答Yes若且為若此答案對l 也是Yes。為
了證明某個NP問題A實際上是NPC問題，證明者必須找出一個已知的NPC問題可以變換成A。
本定義的得到一個結論，就是若上述的C有一個多項式時間可解的演算法，則我們可以將
所有的NP問題降到P之中。
這個定義是史提芬‧古克[1]所提出。雖然NPC這個詞並沒有出現在這篇論文上任何地方。
在這個資訊科學會議上，資訊科學家激動地討論NPC問題是否可以在一個確定型圖靈機上
以多項式時間求解。John Hopcroft總結與會眾人的共識，認為由於沒有人能對某一命題
提出駁倒對方的證明，此問題不會於現在解決。此命題就是知名的
P和NP相等嗎?。
尚未有人能提出證明，說明NPC問題是否能在多項式時間中解決，使得此問題成為著名的
數學中未解決的問題。 劍橋大學的「克雷數學研究所」（Clay Mathematics
Institute, 簡稱CMI）提供了一百萬美金獎金給任何可以證明P=NP或P≠NP的人。
一開始很難相信NPC問題是實際存在的，但著名的古克-李芬定理說明了一切（由Leonid
Levin與Cook獨立證出SAT問題是NPC問題，簡化過但依舊艱深的證明在此）。
在1972年，Richard Karp證明有好幾個問題也是NPC（請見Karp的21個NP完全問題），因
此除了SAT問題外，的確存在著一整類NPC問題。從古克開始，數千個問題藉由從其他NPC
問題變換而證實也是NPC問題，其中很多問題被蒐集在Garey與Johnson於1979年出版的書
之中[2]。
一個滿足條件2但不滿足條件1的問題被稱為NP-hard。正式地說，一個NP-hard問題至少跟
NPC問題一樣難，也許更難！例如在某些任意大的棋盤遊戲走出必勝的下法，就是一個
NP-hard的問題，這個問題甚至比那些NPC問題還難！
範例問題
另一個有趣的例是圖同構(isomorphism)問題，即以圖論方法決定兩個圖是否為同構。兩
圖同構的直覺條件是若其中一圖可以經由移動頂點使它與另一個圖重合，則為同構。 思
考下列兩問題：
圖同構：圖G1是否與圖G2同構？
子圖同構：圖G1是否與圖G2的任一子圖同構？
子圖同構問題是NPC，而圖同構問題一般認為不是P也不是NPC問題，雖然它明顯是一個NP
問題。這是一個典型被認為很難卻還不是NPC問題的例子。
想要證明一個問題是NPC，最簡單的方法是先證明它屬於NP，然後將它變換成某個已知是
NPC的問題。因此在學習變換技巧前，先熟悉各種不同類型的NPC問題是很有用的。下表列
出了一些以決定性命題表示的著名NPC問題：
變換流程圖。布林滿足問題:（Boolean satisfiability problem）（SAT）
N-puzzle問題（華容道問題):(N-puzzle）
郊遊打包問題:（Knapsack problem）
漢彌爾頓迴圈問題:（Hamiltonian cycle problem）
旅行推銷員問題:（Traveling salesman problem）
子圖同構問題:（Subgraph isomorphism problem）
子集合加總問題:（Subset sum problem）
分團問題:（Clique problem）
頂點涵蓋問題:（Vertex cover problem）
獨立頂點集問題:（Independent set problem）
圖著色問題（參見四色定理）:（Graph coloring problem）
更多NPC問題的例子，請見NP-complete問題列表（英文版）。
右邊是一些NPC問題及證明其為NPC問題的變換流程圖。在流程圖中，箭頭代表的是從何問
題變換成另一問題的過程，要注意的是這張圖並不代表這些問題的數學關係，事實上任兩
個本質為NPC的問題都可以以多項式時間變換，這圖僅指示可以讓研究者較為簡單地變換
問題的順序。
通常一個P與NPC問題的敘述看起來只有一些不同的地方，例如3SAT問題（SAT問題的限製
版本）仍然是NPC問題，但更限制的2SAT問題則是個P問題（準確的說，是NL-complete問
題），而條件較為寬鬆的MAX 2SAT問題卻又成了NPC問題。決定一個圖是否能被兩色塗滿
是P問題，但三色圖是NPC問題，即使我們將它限制在平面圖上。決定一個圖有無迴圈或它
是兩分圖很容易（在log空間等級），但是發現一個最大二分圖或最大迴圈子圖則是NPC。
以一固定百分比來求郊遊打包問題的最佳解可以在多項式時間解決，但是求最佳解是NPC
。
[編輯] 折衷的解法
目前為止，所有已知解NPC問題的演算法需要依照資料數量而定的超多項式（
superpolynomial）時間，目前也不知道是否有任何更快的演算法存在。因此要在輸入資
料量大的時候解決一個NPC問題，通常我們使用下列的手段來解：
近似演算法: 這類演算法可以快速發現離最佳解在一定差距內的次佳解。
亂數演算法: 此類演算法可提供一亂數產生的輸入資料，讓本質上解答分佈均勻的受測程
式可以有良好的求解效率。對於解答分佈不均勻的程式，則可以降低亂數程度以改變輸入
資料。
特例: 此演算法可以在題目呈獻某些特殊情況時快速得解。參數化複雜度（
Parameterized complexity）可視為廣義的此類演算法。
啟發式演算法: 這種演算法在許多時候可以產生理性解答（即運用評比或線索找出解），
但無法保證它效率的良莠與解答的好壞程度。
一個啟發式演算法的例子是用在圖著色問題以O（n log n）的貪婪演算法找次佳解，用在
某些編譯器的暫存器配置階段上，此技術又叫圖著色全域暫存器配置（graph-coloring
global register allocation）。每頂點視為一變數，每邊代表兩變數同時使用的情況，
顏色則代表配置給每一變數的暫存器編號。由於大多數的RISC機器擁有大量通用暫存器，
因此啟發式演算法很適合用來解這類題目。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.224.53.178