NP (複雜度)

維基百科,自由的百科全書
前往: 導覽搜尋

非定常多項式英語non-deterministic polynomial,縮寫NP)時間複雜性類,或稱非確定性多項式時間複雜性類,包含了可以在多項式時間內,對一個判定性演算法問題的實例,一個給定的解是否正確的演算法問題。

NP是計算複雜性理論中最重要的複雜性類之一。它包含複雜性類P,即在多項式時間內可以驗證一個演算法問題的實例是否有解的演算法問題的集合;同時,它也包含NP完全問題,即在NP中「最難」的問題。計算複雜性理論的中心問題,P/NP問題即是判斷對任意的NP完全問題,是否有有效的演算法,或者NP與P是否相等。

定義與理解[編輯]

形式化定義[編輯]

目前常用的定義是所謂的「關係定義式」。即對於一個語言L,L在NP中,那麼存在多項式時間圖靈機M,和多項式p使得:

 x \in L \iff \exists y \in \{0,1\}^{p(|x|)}, M(x,y)=1 .

NP的理解[編輯]

理解NP有兩個角度:一個角度是作為確定性圖靈機的一個推廣,另一個角度是作為多項式時間可驗證解的演算法問題的集合。

NP困難問題和NP完全問題[編輯]

要理解這幾個概念, 首先要明白幾件事:
1. 對於NP問題是否存在確定的多項式時間的解,目前還不清楚(即有可能有一天可以證明NP問題=P問題,但目前還證明不出來、也不能證明NP問題≠P問題,目前的結論只是NP問題集  P問題集
2. 問題之間可以規約, 即如果某個NP問題存在確定的多項式時間解,那麼另一個NP問題也存在確定的多項式時間解。這個過程是可以證明的、並且已經被證明。

NP困難問題(NP-hard problems) 是指這樣的一類問題, 它們本身的複雜度是多少無所謂(但由後面的論述可知至少是NP), 但是只要這個問題找到確定的多項式時間的解, 那麼我們可以證明出所有的NP問題都一定存在確定的多項式時間的解. (簡單敘述一下就是, 只要有一個NP困難問題找到P解, 那麼所有NP問題都是P問題.)

NP完全問題(NP-complete problems) 如果一個問題既是NP困難問題又是NP問題, 我們稱之為NP完全問題.

例子[編輯]

比如說,我們不知道81785036517是否為質數,但是要確定277877是否為81785036517因數,我們可以直接拿去除。針對277877來驗證8178503651是否為質數的動作可在多項式時間內完成,故針對某可能解來驗證某數是否為質數的問題是一個NP問題。

再取一個例子,假如一件問題要處理的時間非常大,不是多項式時間內可以完成的, 但是他可以透過無限的計算器去算,最終計算時間複雜度只有O(nk) , 那麼它就是NP(非確定性多項式時間)問題。

所謂的非確定性是指,用極大的數量去解決來達成多項式時間解決的問題。 還有一個典型的例子,就是輸出n個元素的全排列。即使是非確定機,也不能在多項式時間內解決,這是一個NP-hard問題。