NP複雜度

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

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

基本介紹

• 中文名：NP複雜度
• 外文名：non-deterministic polynomial
• 分類：複雜度類

定義與理解

形式化定義

常用的定義是所謂的“關係定義式”。即對於一個語言L，L在NP中，那么存在多項式時間圖靈機M，和多項式p使得：

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完全問題。

例子

比如說，我們不知道81,785,036,517是否為素數，但是要確定277,877是否為81,785,036,517因數，我們可以直接拿去除。針對277,877來驗證8,178,503,651是否為質數的動作可在多項式時間內完成，故針對某可能解來驗證某數是否為質數的問題是一個P問題。

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

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