p和NP问题

p是可以在多项式时间内求解的问题，NP是可以在多项式时间内验证给定答案正确性的问题。尽管定义复杂，但P=NP实际上是在问:

如果能快速验证答案的对错，是不是也能快速计算出来？

p是英语单词多项式的第一个字母。什么样的问题叫P型问题？

如果一个问题能找到一个能在多项式时间内求解的算法，那么它就属于P类问题。

信息奥赛的题目都是P型问题，因为用穷举法得到的一个非多项式时间超时程序，不会覆盖任何有价值的算法。！对应的NP问题是什么？

对于一个问题的解，可以在多项式时间内验证解的正确性。

一个例子:

有人得到一个求最短路径的问题，问有没有从起点到终点长度小于100单位的路径。她根据数据集画了一张地图。这个时候她太幸运了，接连得到一条路径，算到96个单位。现在这个问题的答案通过证明给出了。

在这个问题中，很难找到解决方案，很容易验证一个解决方案。只需要O(n)的时间复杂度。对于给定的路径，可以在多项式时间内验证，这是NP问题。

有没有一个不是NP难的问题？当然可以。只要问题的解不能在多项式时间内得到验证，问题就不是NP难的。哈密尔顿回路问题，因为验证一条路径是否经过每个顶点是非常容易的。如果把哈密尔顿问题改成这样:问一个图中是否不存在哈密尔顿圈。除非你试过所有的路径，否则你无法回答这个问题。

通常只有NP问题才能是P类问题。我们不期望一个连多项式时间都验证不了一个解的问题，会有一个多项式级别的算法来解决。到这里你会意识到“NP问题”其实是在讨论NP问题和P问题的关系。

问与答:

NP代表非多项式吗？(NP代表非多项式)

非确定性多项式(非确定性多项式，如果是确定性多项式，则成为P问题)

知乎-量子通信-参考地址

关于P和n P问题的参考博文