NP完全问题

**NP 完備**或 **NP 完全** （**NP-Complete**，縮寫為 **NP-C** 或 **NPC**），是計算複雜度理論中，決定性問題的等級之一。NP 完備是 NP 與 NP 困難問題的交集，是 NP 中最難的決定性問題，所有 NP 問題都可以在多項式時間內被歸約（reduce to）為 NP 完備問題。倘若任何 NP 完備問題得到多項式時間內的解法，則該解法就可應用在所有 NP 問題上，亦可證明 NP 問題等於 P 問題，然而目前為止並未發現任何能在多項式時間內解決 NP 完備問題的方法。

## 正式定義

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

1. 它是一個 NP 問題
2. 它是一個 NP 困難問題
3. 其他屬於 NP 的問題都可在多項式時間內歸約（reduce to）成它。

**可歸約**（reducible）在此意指對每個問題 _L_，總有一個多項式時間多對一變換，即一個決定性的演算法可以將實例 _l_ ∈ _L_ 轉化成實例 _c_ ∈ _C_，並讓 _c_ 回答 Yes 若且唯若此答案對 _l_ 也是 Yes。為了證明某個 NP 問題 _A_ 實際上是 NP 完備問題，證明者必須找出一個已知的 NP 完備問題可以歸約成 _A_。

本定義得到一個結論，就是若上述的 _C_ 有一個多項式時間可解的演算法，則我們可以將所有的 NP 問題降到 P 之中。若欲證明一個問題是 NPC，最簡單的方法是先證明它屬於 NP，然後將「某個已知是 NPC 的問題」歸約成它。

## 歷史

前述定義是史提芬・古克[1]所提出。雖然 NPC 這個詞並沒有出現在這篇論文上任何地方。在這個資訊學會議上，資訊學家激動地討論 NPC 問題是否可以在一個確定型圖靈機上以多項式時間求解。John Hopcroft 總結與會眾人的共識，認為由於沒有人能對某一命題提出駁倒對方的證明，此問題不會於現在解決。此命題就是知名的

　
: **P 和 NP 相等嗎？**。尚未有人能提出證明，說明 NPC 問題是否能在多項式時間中解決，使得此問題成為著名的數學中未解決的問題。位於美國麻省劍橋市的「克雷數學研究所」（Clay Mathematics Institute，簡稱 CMI）提供了一百萬美元獎金給任何可以證明 P=NP 或 P≠NP 的人。

一開始很難相信 NPC 問題是實際存在的，但著名的古克 - 李芬定理說明了一切（由 Leonid Levin 與 Cook 獨立證出 SAT 問題是 NPC 問題（即 Cook-Levin 理論）。

在 1972 年，理察・卡普證明有好幾個問題也是 NPC（請見卡普的二十一個 NP - 完備問題），因此除了 SAT 問題外，的確存在著一整類 NPC 問題。從古克開始，數千個問題藉由從其他 NPC 問題變換而證實也是 NPC 問題，其中很多問題被蒐集在 Garey 與 Johnson 於 1979 年出版的書之中[2]。

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

## 例子

### 子集合加總問題

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

　
: 給予一個有限數量的整數集合，找出任何一個此集合的非空子集且此子集內整數和為零。

　
: 意即： $S$ 是一個包括若干整數的集合，找出任一一個 $S'\subset S$ 且 $\sum _{x\in S'}x=0$

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

### 圖同構問題

另一個有趣的例是圖同構（isomorphism）問題，即以圖論方法決定兩個圖是否為同構。兩圖同構的直覺條件是若其中一圖可以經由移動頂點使它與另一個圖重合，則為同構。思考下列兩問題：

* 圖同構：圖 G1 是否與圖 G2 同構？
* 子圖同構：圖 G1 是否與圖 G2 的**某一子圖**同構？

子圖同構問題是 NPC，而圖同構問題一般認為不是 P 也不是 NPC 問題，雖然它明顯是一個 NP 問題。這是一個典型被認為很難卻還不是 NPC 問題的例子。

### 其他

下表列出了一些以決定性命題表示的著名 NPC 問題：

* 布林滿足問題
* N-puzzle 問題（華容道問題）
* 背包問題
* 漢彌爾頓迴圈問題
* 旅行推銷員問題
* 子圖同構問題：（Subgraph isomorphism problem）
* 子集合加總問題
* 分團問題
* 頂點覆蓋問題：（Vertex cover）
* 獨立頂點集問題：（Independent set 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 機器擁有大量通用暫存器，因此啟發式演算法很適合用來解這類題目。

## 其他歸約法

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

另一種歸約法稱為多項式時間圖靈歸約（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 的定義是否會因為使用不同變換手法而產生差異，仍是一個未知的問題。

## 參見

* NP-complete 問題列表
* 幾乎完備問題與弱完備問題
* ASR-complete
* Ladner 理論
* NP 困難
* P/NP 問題
* 三維匹配問題

## 參考文獻

### 參照

### 書籍

* **^** S. A. Cook. The complexity of theorem proving procedures, Proceedings, Third Annual ACM Symposium on the Theory of Computing. New York: ACM. 1971: 151–158.
* **^** Garey, M.; D. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1979. ISBN 978-0-7167-1045-5.  （此書是發展此理論及集多種問題的經典）
* Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202. [2006-11-23]. （原始內容存檔於 2006-11-25）.
* Pierluigi Crescenzi; Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems. Stockholm: KTH NADA. [2006-11-23]. （原始內容存檔於 2006-12-05）.
* Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. NP-Completeness. Introduction to Algorithms Second Edition. MIT Press and McGraw-Hill. 2001: 966-1021. ISBN 978-0-262-03293-3.  引文格式 1 維護：冗餘文字 (link)
* Michael Sipser. NP-completeness, Additional NP-complete Problems. Introduction to the Theory of Computation. PWS Publishing. 1997: 248-271. ISBN 978-0-534-94728-6.
* Christos Papadimitriou. NP-complete problems. Computational Complexity 1st edition. Addison Wesley. 1993: 181–218. ISBN 978-0-201-53082-7.  引文格式 1 維護：冗餘文字 (link)

### 網頁

* Computational Complexity of Games and Puzzles（頁面存檔備份，存於網際網路檔案館）
* Tetris is Hard, Even to Approximate
* Minesweeper is NP-complete!