2000年初，美国克雷数学研究所选定了7个“千禧年大奖难题”：NP完全问题、霍奇猜想、庞加莱猜想、黎曼猜想、杨-米尔斯存在性和质量缺口、纳卫尔-斯托克方程和BSD猜想。NP完全问题位于这个数学难题清单的第一项，是计算机科学领域最大的难题，也可能是所有数学问题中最难的一项。P完全问题即P=NP?问题由史蒂芬·库克在1971首次提出，它是七大千禧年大奖问题中最年轻的问题，同时也是最好理解的一个。
什么是P和NP？
在我们的生活中，有些数学问题可以很快地解决，比如买东西结账；但是有些数学问题却要花大量的时间去解决，比如下象棋。随着数学和计算机科学的发展，针对于部分比较难解决的数学问题，人们想出了更好的算法，所以解决它们需要的时间就变少了。将问题分为快速解决和慢速解决两种的话，加减乘除是可以快速解决的问题，而下象棋是慢速解决的问题，当然还有许多的问题，我们不清楚应该将它们分于哪一类。于是我们就用了包含P与NP的更精准的定义去分类这些数学问题。
P问题包含所有可以被计算机程序快速解决的问题，比如加减乘除。NP问题是指如果给出一组问题的答案，你至少可以在合理的时间里检查这个答案是否正确。例如给定一个数41607317，如果对这个较大数做质因数分解，是有些难度的。但是如果给出一个可能的答案比如8699和4783，你可以通过将两个数相乘对比原来的大数，很快地得出8699和4783这两个数是正确答案。世界上有很多的问题，我们很难去找到它的答案，但是如果给出了答案，验证这个答案是否正确却是相对简单的。例如，做出数独的答案，可以很简单的验证结果的正误，但是我们至今没有找到一个可以完美解决所有数独问题的最优途径（想象1000×1000级的数独，而不是9×9的），做数独往往还是用试数的方法（即枚举法）。
毫无疑问，NP问题包含P问题，因为对于P问题只需按部就班地算出问题的答案进行对比就可以了。
最难的NP问题与NP的外界
所有人都认为NP所包含的问题比P所包含的问题要多，即使有些问题还没有被发现，当然现在还没有人能够证明这一点。数学家发现很多NP问题其实是互通的，比如数独问题的本质和蛋白质折叠问题是一样的，如果你能找到解决数独问题的最优算法，蛋白质折叠这一21世纪最重要的生物学问题也将迎刃而解。数独和蛋白质折叠问题属于NP中的一个下属分类NPC（NP-Complete）问题。NPC问题是NP中最难的一部分，这些问题的复杂性（解决问题需要的时间和空间）与整个类的复杂性相关联，如果我们能快速解决某一NPC问题，那么所有的NP问题都能快速解开。
NP问题需要花很长的时间去求解，但是很容易验证结果的正确性。在NP之外，还存在着一些问题，验证这些问题的结果甚至都是不可能的，例如，我们很难判断象棋中的某一步是不是最好的。还有Co-NP问题，与NP问题不同的是，Co-NP问题可以在合理的时间内很容易地排出错误解，而不是验证正确解。Co-NP问题与NP问题是否是互通的，我们也不得而知。除此之外，还有非常多的问题分类，每一个分类都需要花费大量的时间去解释。
P=NP？
NP是举足轻重的，因为它包含了一些非常重要的问题，比如：旅行商问题（给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路），电路设计问题和数据库问题等，如果这些问题得到解决，我们的生活将会有翻天覆地的变化。因此，数学家们一直积极地解决各种数学问题。在这个努力的过程中，我们有时会幸运地发现一些NP问题实际上是P问题，我们就找到了解决这个问题的捷径，同时仍有很多的NP问题还不能被归类为P。科学家开始思考：NP中的所有问题最终都会变成P问题吗？还是有些NP问题就是比P问题难解决的多？这就是著名的P=NP？问题。
解决P=NP猜想的方法有两种，一种是找到NP问题的解决算法，那么所有的NP问题就都可以解决了；另一种就是从数学理论上证明这样的算法不存在。但是现在的很多数学家在证明这一问题上存在误区，他们往往假设一种可能的解决算法，然后设法证明这种算法的错误性或不存在。实际上证明P=NP问题本身就是NP问题之一，这让我们感到更加的困惑。
如果P=NP，那么我们就能找到简单的解决问题的方法，换言之，就是人类在解决复杂问题的时候是有捷径的。计算机一下子就可以变得非常的“聪明”，可以在十分混乱的局面中，快速找到一个捷径。当获知了所有的信息以后，计算机可以在极短的时间里，对证券市场、天气、球赛结果做出非常准确的预测；计算机能够轻松找到一个算法，来知道艺术作品是如何直击人心的，于是计算机可以为每个人定制出他最喜爱的音乐、艺术作品。与此同时，人工智能可以快速的自我优化，意味着人类的末日可能到来了；密码学的基础也很容易就会被破解，我们每个人都毫无秘密可言。
P=NP吗？数学家还没有答案。
联系客服
