现在我回到P vs NP。

通俗说，P（Polynomial）指计算机求解容易的问题，即存在多项式时间精确算法，比如GPS中寻找任意二个地点之间的最短距离。

NP（Non-deterministic Polynomial）指计算机求解困难的问题，比如视频举的3个例子：3-图染色问题，背包问题，合取范式可满足问题（SAT问题），这些问题只有精确求解的指数时间穷举法，或多项式时间近似算法。

在人们的常识认知中，NP与P是不同的，但是当人们希望对NP做深入的了解时，学界告诉人们：NP是其解可以容易验证的问题，比如：视频中3-图染色问题的例子，给图用3种颜色着色，可以容易验证此着色是否满足相邻两点是否着同一色。

接着又说，当然P也是其解可以容易验证的问题，现在问题是：“NP是否等于P？” - 这就是“世纪难题P vs NP”！

你们怎么看这个问题？这样的NP定义方式与前面Louis回答我“什么是马？”是否似曾相识（与法国朋友漫谈P vs NP（1））？

参考文献：

【1】https://www.youtube.com/watch?v=8TrIW-4kfRg

【2】May 2, 2013 (The New Yorker)，A Most Profound Math Problem， Alexander Nazaryan。中文译文：http://blog.sciencenet.cn/blog-2322490-995211.html