P问题：多项式时间内可以找到解的问题，这个解可以在多项式时间内验证。
NP问题：有多项式时间内可以验证的解的问题，而并不能保证可以在多项式时间内找到这个解。
比如汉密尔顿回路，如果找到，在多项式时间内很容易验证这个解，但并不能保证在多项式时间内一定
可以找到这个解。如果运气好，可能找到，运气不好，可能找不到。也就是非确定性图灵机可以在多项式时间内解决。
NP不是P的否定。而是P的外延，也就是超集。
NP中的N是non-determinitive的意思，也就是非确定性，而不是单纯的非。
我们常说的NP问题实际上是指NPC,也就是NP-complete问题。这是NP范围内最不可能在多项式时间内找到解的问题。
NPC目前没有人找到多项式时间的解法，同时数学上也没有人证明它没有多项式时间的解法。
但它是NP问题集合内被认为最不可能有多项式时间解法的，一般认为是与P互斥的。
而且解决了一个NPC，就解决了所有的NP问题。也就是说解决了一个NPC问题，就证明了NP=P。
但遗憾的是目前为止，并没有人能解决。
NP=P? 这个问题也就没人知道。
另外：
这篇博文非常好，一定要看！。
http://www.matrix67.com/blog/archives/105#comment-1159492