NP (複雜度)

非決定性多项式集合（英語：non-deterministic polynomial，缩写：NP）是计算理论中最重要的集合之一，它包含P和NP-complete。

P問題是指在多项式时间内，可以找出解的決定性問題(decision problem)，而NP問題則包含可在多项式时间內驗證其解是否正確，但不保證能在多項式時間內能找出解的決定性問題。NP包含P和NP-complete问题, 因此NP集合中有簡單的問題和不容易快速得到解的難題。

“NP是否等於P”是计算机科学中知名的難題。

定义与推論

決定性問題

一個決定性問題(decision problem)是指其輸出，只有「是」或「否」的問題。例如，搜尋問題為詢問 x 是否出現在一個集合 A 中?若有則輸出「是」，否則輸出「否」。

P問題

當一個決定性問題存在一個能在多項式時間內找出解的演算法時，則稱此問題落在P 的集合中。

有一些決定性問題，人類目前尚無法將他們歸入集合 P 中。為了思考這些問題，於是在一般演算法可採用的功能上，擴增以下虛構的新指令。這些新指令雖然不存在於現實中，但是對探討這些難題的性質及彼此的關係，有很大的幫助。以下是這些虛構的新指令：

1. choice(S)：自集合 S 中，選出會導致正確解的一個元素。當集合 S 中無此元素時，則可任意選擇一個元素。

2. failure()：代表失敗結束。

3. success()：代表成功結束。
其中 choice(S)可以解釋成，在求解的過程中，神奇地猜中集合 S 中其中一個元素，使其結果是成功的；並且這三個指令只需要 O(1)時間來執行。當然，choice(S) 是如何快速猜中的，在此是不需討論的，因為畢竟它只是虛構的。在添加這些虛構功能後，所設計出的演算法，被稱為非決定性演算法(non-deterministic algorithm)；相較之下，原來一般的演算法，就稱為決定性演算法(deterministic algorithm)。利用非決定性演算法，我們定義出另一個集合 NP。

NP問題

當一個決定性問題的解能在多項式時間內被驗證時，則稱此問題落在NP 的集合中。

滿足問題 (satisfiability problem，簡稱 SAT)，就是一個NP中的典型問題。

滿足問題(SAT)

令 x ₁，x ₂，…，x _n 代表布林變數(boolean variables)(其值非真(true)即假(false)的變數)。令-x_i 代表 x_i 的相反數(negation)。一個布林公式是將一些布林變數及其相反數利用而且(and)和或(or)所組成的表達式。滿足問題是判斷是否存在一種指定每個布林變數真假值的方式，使得一個布林公式為真。

輸入:一個 n 個變數的布林公式

例如: (-x ₁∨ -x ₂ ∨ x ₃)∧ (x ₁ ∨ x ₄)∧(x ₂ ∨ -x ₁) 其∨代表(or)，∧代表(and)。輸出:是否存在一種指定每個布林變數真假值的方式，使得此公式為真？例如: 是(當 x ₁=真，x ₂=真，x ₃=真，x ₄=真時，此公式為真)

利用滿足問題可以定義出NP-hard和NP-complete。但是我們需要一個問題轉換的概念。問題轉換技巧，其所需要轉換的時間皆需在多項式時間(即 O (n^k))內完成。利用此多項式時間的轉換，我們可以將 NP中的難題建立起一些有趣的關係。

問題轉換:針對兩個問題 A 和 B ，如果存在一個 O (n^k)時間的(決定性)演算法，將每一個問題 A 的輸入轉換成問題 B 的輸入，使得問題 A 有解時，若且唯若，問題 B 有解。此關係被稱為，問題 A 轉換成(reduce to)問題 B ，可表示成 A ∝ B 。

一個問題 L 被稱為是 NP-hard，若且唯若，滿足問題轉換成 L(即滿足問題∝L)。滿足問題是 NP 中的難題，而 NP-hard 的問題則是滿足問題衍生(轉換)出來的。

一個問題 L 被稱為是 NP-complete，若且唯若，L ∈NP 而且 L ∈NP-hard。

史蒂芬庫克(Stephen Cook)證明了一個十分重要的性質：

性質(A)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成滿足問題。」

性質(B)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-complete 問題。」

性質(C)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-hard 問題。」

性質(D)：「滿足問題在集合 P 中，若且唯若，P=NP。」

例子

比如說，一個決策性問題:輸入一個整數x, 請回答x是否為偶數(even number)。我們利用一個程式判斷x除以2是否整除即可得到最後結果。此程式是決定性演算法, 並且其時間複雜度為O(1)=O(n⁰), 因此此問題落入P集合中。

再舉一個例子，下面是滿足問題的一個非決定性演算法。

Algorithm satisfiability (E (x ₁, … , x_n ))

{ Step 1: for i =1 to n do

x_i ←choice (true, false) /*利用 choice 直接猜中 x_i 的真假值*/

Step 2: if E (x ₁, … , x _n) is true then success () /*計算此布林公式是否為真*/

　　　 else failure ();
}

上述的非決定性演算法的時間複雜度為O(n¹)即代表滿足問題落入NP集合中。

參見

NP完全問題

参考文献

引用

^ R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site （页面存档备份，存于互联网档案馆）.

来源

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 34.2: Polynomial-time verification, pp. 979–983.
Michael Sipser. Sections 7.3–7.5 (The Class NP, NP-completeness, Additional NP-complete Problems). Introduction to the Theory of Computation. PWS Publishing. 1997: pp. 241–271. ISBN 0-534-94728-X.
David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3rd edition, 2004.

俞征武, 發現演算法, 旗標出版股份有限公司, 2017.

外部連結

Complexity Zoo: NP^{[失效連結]}
Graph of NP-complete Problems^{[失效連結]}
American Scientist primer on traditional and recent complexity theory research: "Accidental Algorithms"（页面存档备份，存于互联网档案馆）

[1] R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. ACM site （页面存档备份，存于互联网档案馆）.

[1]