NP问题
P问题和NP问题
- P问题 (Polynomial Solvable):
如果一个判定问题是P问题，则这个问题存在一个多项式解法。 即图灵机只需要多项式时间就可以得到答案, 既回答yes或者no。
- NP问题(Nondeterminstic Polynomial Solvable):
如果一个判定问题是NP问题， 则这个问题的一个可能的解，可以在多项式时间内被验证是否正确。 其实这不是本来的定义。 本来的定义是，NP问题是非确定性图灵机有多项式解。 但我们可以把非确定性图灵机多项多可解转化成确定性图灵机多项式可验证解。 确定性图灵机更好好理解，所以用那个定义。
P问题是确定性图灵机在多项式时间内求到解，NP问题是非确定性图灵机在多项式时间内求到解，或者说NP问题是确定性图灵机在多项式时间内验证解.
所以NP问题比P问题更难。 就像前面有人说的，改卷的老师会验证题目的答案是否正确，但他不一定会做这些题。
NPC 和 NP-hard
- NPC, 即NP完全性问题。 是指NP问题中的最难的问题。 即还没有找到多项式解法，但多项式可验证。 而且只要一个NPC问题有多项式解法，其它所有NP问题都会有一个多项式解法。
- NP-hard是指所有还没有找到多项式解法的问题, 并没有限定属于NP。 所以NP-hard比NPC范围更大，也会更难。 NPC是NP-hard和NP的交集.
关系
P 属于 NP。 就是说，一个问题如果属于P， 则一定属于NP。 (这里P, NP表示符合定义的相关问题的集合)
反过来则不一定，7大数学世纪难题之一就是问 P是否等于NP。
多项式的时间
一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。