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问题。