为什么P和NP问题价值百万

在2000年美国克雷数学研究所公布的千禧年七大数学难题中，P和NP问题排在了第一位。第一个解决该问题的人将会获得100万美元的奖金。

P和NP问题源自强大的计算机在面对指数级问题时遇到的困境。大家或许已经发现，指数级别的运算次数往往只是针对最坏情况而言的。在前文所述子集和问题中，给定一组数据后，如果这组数据确实有满足要求的解，计算机程序完全有可能瞬间找到这个解——如果它的运气足够好的话。运气最好的情况下，计算机尝试的第一个方案就满足要求，总共需要的运算次数不超过$n$次。对于某一个问题，如果在最好的情况下，计算机只需要多项式级别的运算就能找到一个解，我们就把它叫作NP问题。

并非所有的问题都是NP问题。即使计算机一下就猜到了正确的解，它也必须肯定这确实是一个正确的解。考虑这么一个问题：给定一个象棋棋局，问黑方是否有必胜策略。我们目前没有一种算法能够在多项式的时间里判断一个策略是不是必胜策略，因此这个问题很可能不是一个NP问题。因此，NP问题还有另一个等价的定义：对于某个问题来说，如果我们能够在多项式的时间里验证它的某个解的正确性，这个问题就是一个NP问题。

拥有多项式算法的问题就是P问题，显然，所有P问题都是NP问题。既然能在多项式的时间里找到一个解，首先肯定要能在多项式的时间里验证解的正确性。1971年，加拿大科学家史蒂芬·库克提出了这样一个问题：所有的NP问题也都是P问题吗？换句话说，所有能够轻易验证一个解的问题，也都能轻易地寻找到一个解吗？这就是计算复杂度理论乃至整个计算机科学中最重要、最核心，同时也是最激动人心的问题。我们把这个问题叫作“P和NP问题”，或者更简单地说：P=NP吗？

目前，科学家们普遍认为，P是不等于NP的。这是因为，科学家找到了一类特殊的NP问题，它们是所有NP问题中最困难的问题。这类特殊的NP问题叫作NP完全问题。科学家已经发现了上千种NP完全问题，绝大多数都是看上去非常简单非常容易理解的问题，刚才我们讲到的子集和问题便是一个典型的NP完全问题。然而，不管怎么努力，人们都没有找到哪怕一个NP完全问题的多项式算法，可见NP完全问题有多困难。事实上，只要任何一个NP完全问题有了多项式的算法，那么包括其他NP完全问题在内的所有NP问题也都会有多项式的算法，P也就等于NP了。看来，为NP完全问题找到一个多项式级别的算法，这应该是一件极不可能的事情。

目前科学家既没有证明P≠NP，也没有证明P=NP。不过，人们始终对这个问题抱有极大的兴趣。

普林斯顿大学计算机学院外墙上用凸起的砖块表示用二进制描述的P和NP问题 早期普林斯顿大学全景