理解P/NP问题

今天在学习时候突然看到了经常出现的NP完全问题，之前一直没在意这是一个什么问题，今天仔细的搜索理解了一下，给大家伙谈谈我的理解，有不对的请大家指正。

到底什么是 P/NP 问题

简单来说就是

P(Polynomial)问题：在多项式时间内被验证的问题
NP(Nondeterministic Polynomially)问题：能否证明在多项式时间内找到这个问题的解
P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。

多项式时间

多项式的一般表达式为$a_0$+$a_{1}x$+$a_2$$x^2$+…+$a_k$$x^k$
但求解问题的规模为n时，最坏求解时间是O($n^k$),这就是多项式的算法。

例如：

P vs. NP 是一个非常重要的，未被解决的计算机问题。2000年，克雷顿数学研究所，发布了7个数学难题（Millennium Prize Problems），每个奖励100万美金，其中就有P vs NP问题。

P代表多项式时间。我们发现现实生活中有一类问题，可以在多项式时间（比如 O($n^2$) 等等）内被验证。虽然可以在多项式时间被验证，但是往往不容易解决， 我们将这类问题归类成NP问题。 所以NP问题，本质上是一类在我们可以接受的时间范围内可以被验证的问题。

比如说数独问题，验证很容易，只要遍历行和列去检查就可以了是一个O(n^2)的算法，但是求解很困难。尤其是很大的数独，比如1000*1000的数独。

再比如说，求地图上两点的最短路径，我们可以轻松的在多项式时间内解决。

但是这些可以被计算机验证的问题，可以被计算机解决吗？ 于是我们得到一个疑问：数独问题也可以在多项式时间内解决吗？ 如果可以，那么P=NP；如果不可以，那么 P$\ne$NP。

究竟P=NP还是P$\ne$NP 呢？ 这就是P vs NP问题。 这个问题我们不知道答案，如果谁发现了答案，那么可以得到100万美金的奖励。

推荐阅读：浅谈P vs. NP