NPC問題

他們發現NP中的某些問題的複雜性與整個類的複雜性相關聯。這些問題中任何一個如果存在多項式時間的演演算法，那麼所有NP問題都是多項式時間可解的。這些問題被稱為NP-完全問題(NPC問題).

p問題，可以在多項式時間內解決的問題，polynomial problem。

np 問題，可以在多項式的時間裡驗證一個解的問題，non-deterministic polynomial

npc問題，是NP的一個子集，且其中每一個問題均能由NP中的任何問題在多項式時間內轉化而成，np complete

判定方法:

一個判定性問題，滿足：

(1)∏∈NP

(2)對任意一個∏’∝poly∏ (注:poly為規約符號)

則問題∏稱為NP-完全的(NP-complete，NPC)；如果問題∏僅滿足條件(2)而不滿足條件(1)，則問題NP稱為NP-難的(NP-hard)。

在計算複雜度理論的世界中， NPC問題，又稱 NP完全問題或 NP完備問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。許多人推測若 任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。

一個NPC問題的例子是子集合加總問題，題目為

給予一個有限數量的整數集合，找出任何一個此集合的非空子集且此子集內整數和為零。意即： S是一個包括若干整數的集合，找出任一一個 S′⊂ S且

這個問題的答案非常容易驗證，但目前沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間複雜度是Ο（2），n是此集合的元素數量。

假設 P ≠ NP的複雜度類的圖解。若 P = NP則三類別相同。

一個決定性問題 C若是為NPC，則代表它對NP是完備的，這表示：

它是一個NP問題，且

其他屬於NP的問題都可歸約（reducible）成它。

可歸約在此意指對每個問題 L，總有一個多項式時間多對一變換，即一個決定性的演演算法可以將實例 l ∈ L 轉化成實例 c ∈ C，並讓 c 回答Yes當且僅當此答案對 l 也是Yes。為了證明某個NP問題 A實際上是NPC問題，證明者必須找出一個已知的NPC問題可以變換成 A。

本定義得到一個結論，就是若上述的 C有一個多項式時間可解的演演算法，則我們可以將所有的NP問題降到P之中。

這個定義是史提芬·古克所提出。雖然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（請見卡普的二十一個NP-完全問題），因此除了SAT問題外，的確存在著一整類NPC問題。從古克開始，數千個問題藉由從其他NPC問題變換而證實也是NPC問題，其中很多問題被搜集在Garey與Johnson於1979年出版的書之中。

滿足條件2（無論是否滿足條件1）的問題集合被稱為NP-hard。一個NP-hard問題至少跟NPC問題一樣難。有一類問題已經被證明屬於NP-hard但不屬於NP，即，這類問題至少與NP-complete一樣難，但這類問題又不屬於NP（自然也不屬於NP-complete）。例如圍棋的必勝下法，就是這樣一個問題。

另一個有趣的例是圖同構（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問題列表（英文版）。

通常一個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機器擁有大量通用暫存器，因此啟髮式演演算法很適合用來解這類題目。

依照上述NPC的定義，所謂的變換其實是多項式時間多對一變換的簡稱。

另一種化約法稱為多項式時間圖靈歸約（polynomial-time Turing reduction）。若我們提供一個副函式（subroutine）可以在多項式時間解出"Y"，又可寫出呼叫此副函式的程式並在多項式時間解出問題"X"，代表我們可以將"X"多項式時間圖靈變換成"Y"。相較起來，不同處在於多對一變換隻能呼叫上述副函式 一次，且副函式的回傳值必須 就是整個變換程式回傳的值。

如果有人使用圖靈變換而非多對一變換來解析NPC，此問題的解答集合不一定會小於NPC。孰大孰小其實是個開放問題。如果兩個概念相同，則可導出NP=反NP（co-NP）。此結論成立的道理在於NPC與反NPC的定義以圖靈歸約來看是相等的，且圖靈變換定義的NPC包含多對一變換定義的NPC，反NPC也是相同情況。所以若是兩種變換定義的NPC一樣大的話，反NPC也會比照辦理（在兩者的定義之下）。例如SAT的反問題也會是NPC（在兩者的定義之下）。因此推得NP = 反NP（證明在反NP條目中）。雖然NP是否等於反NP是個開放問題，但一般認為這似乎不大可能，也因此那兩類的NPC定義也不大可能相等。

另一種很常用於NPC證明的變換手法是對數空間多對一變換（logarithmic-space many-one reduction），它是一種可以在對數量級空間運用的多對一變換法。由於每道可以在對數空間完成的運算也可以在多項式時間做完，因此能使用對數空間多對一變換的場合也可以使用多項式時間多對一變換。本方法較多項式時間多對一變換優雅，它也可以讓我們對演演算法複雜度細分出更多分類，例如P完備複雜度。而NPC的定義是否會因為使用不同變換手法而產生差異，仍是一個未知的問題。