通过宴会主人的暗示，找到小A女士，就是p类问题；
而你按照他的提示发现自己认识小A女士，容易检查到小A女士就是Np问题。
在某岛国作家《嫌疑人x的献身》推理中，石神和汤川曾讨论，解决一个命题和判断一个命题是否正确，哪个更难。
其实数学界早就已经给出了答案，p=Np？问题就放在哪里，它告诉了所有人，生成问题的一个解，通常比验证一个给定的解，要花费更多时间。
比如，如果让你计算世界上所有原子个数的总和，这个问题很困难，甚至无解。
但是，如果有人告诉你世界上一共有500个原子，那么你能很快验证他是错的。很容易验证，却不容易求解，这种就是Np类问题。
p类问题是可以在多项式时间内解决并验证的一类问题;Np类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。
很显然，所有p类问题都属于Np类问题，但是无法确定Np是否等于p。
而自「p=Np?」提出以来，无论是数学界也好，还是计算机领域也好，都做了很多尝试。
要证明p=Np，最显然的方法就是给出一个Np完全问题的多项式时间的算法。
但在过去的几十年里，一大批数学家和程序人员为寻找Np完全问题的多项式时间的算法做了很多工作，都没有成功。
内容未完，下一页继续阅读