NP (複雜度)
![](https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/300px-P_np_np-complete_np-hard.svg.png)
非決定性多项式集合(英語: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 1,x 2,…,x n 代表布林變數(boolean variables)(其值非真(true)即假(false)的變數)。令-xi 代表 xi 的相反數(negation)。一個布林公式是將一些布林變數及其相反數利用而且(and)和或(or)所組成的表達式。滿足問題是判斷是否存在一種指定每個布林變數真假值的方式,使得一個布林公式為真。
輸入:一個 n 個變數的布林公式
例如: (-x 1∨ -x 2 ∨ x 3)∧ (x 1 ∨ x 4)∧(x 2 ∨ -x 1) 其∨代表(or),∧代表(and)。 輸出:是否存在一種指定每個布林變數真假值的方式,使得此公式為真? 例如: 是(當 x 1=真,x 2=真,x 3=真,x 4=真時,此公式為真)
利用滿足問題可以定義出NP-hard和NP-complete。但是我們需要一個問題轉換的概念。 問題轉換技巧,其所需要轉換的時間皆需在多項式時間(即 O (nk))內完成。利用此多項式時間的轉換,我們可以將 NP中的難題建立起一些有趣的關係。
問題轉換:針對兩個問題 A 和 B ,如果存在一個 O (nk)時間的(決定性)演算法,將每一個問題 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(n0), 因此此問題落入P集合中。
再舉一個例子,下面是滿足問題的一個非決定性演算法。
Algorithm satisfiability (E (x 1, … , xn ))
{
Step 1: for i =1 to n do
xi ←choice (true, false) /*利用 choice 直接猜中 xi 的真假值*/
Step 2: if E (x 1, … , x n) is true then success () /*計算此布林公式是否為真*/
else failure ();
}
上述的非決定性演算法的時間複雜度為O(n1)即代表滿足問題落入NP集合中。
參見
[编辑]参考文献
[编辑]引用
[编辑]来源
[编辑]- 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"(页面存档备份,存于互联网档案馆)
|
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.