个人演唱会还有

3680天

2000年5月，著名的克雷数学研究所提出了“世界七大数学难题”，其中的第一个问题便是NP完全问题，它所探讨的是P=NP是否成立，那么这个P=NP究竟是个什么呢？今天我就试图给你编出来。

P是否等于NP，对于21世纪的人类来说至关重要，因为这个神秘的问题正处于计算机科学与数学的交汇处。事实上，P=NP问题是“计算复杂性理论”的一部分，它所讨论的是计算机处理能力的极限。我们知道，计算机的工作必须依赖于算法，也就是一系列需要执行的命令。在完成某些任务时，计算机只需要几微秒就可以实现，但另一些，以目前的计算机算法处理速度则可能需要几十亿个世纪。

由此可见，算法的效率就是一个至关重要的问题。比如说，计算机经常要做的一件事就是排序，有可能是按照字母表，也有可能是按照数字大小，有可能是升序，也有可能是降序。现在对5,3,4,2,1五个数字进行升序排序，对于我们人类来说，这太简单的，你要是给幼儿园小孩儿出这道题，人家都会以为你是在骂他，因为我们人类知道应该以什么顺序排序，至于我们大脑怎么运转的，那就不知道，总是我们就是会。那么让一台计算机来完成这个任务，它会怎么办呢？目前，一种常用的算法是“冒泡”排序法，这个算法的过程是，按照一种有规律的方式来考察相邻的数对，如果其中一个大于另一个，要么将它们交换为所需的顺序，要么当它们处于正确顺序时保持不动。

所以，对于5,3,4,2,1的升序排列，计算机就会这样来做：首先比较5和3，发现5比3大，然后将二者调换位置。接着看第二个数对，发现5比4也大，于是又把5和4也交换顺序，以此类推，结果经过这样的四次比较后，5就成功地“冒泡”了，到达了它的正确位置，也就是序列的最末端。然后再从头开始比较，首先是3和4，位置保持不变，然后是4和2。最后我们发现，只需经过10次比较，计算机就可以得到准确的数列。

对n数个进行排序也一样，计算机也可以通过这一方法来完成任务，而且其所需的步骤数存在一个界限，这就是n的平方。像这样的如果某个问题，可以在n的幂次步骤数内解决，就被称为可以在“多项式时间”内解决的问题，这就是P问题。这样的算法就是高效率算法，计算机可以轻松地处理这些问题。

那么什么样问题不存在高效率算法呢？最典型的就是“推销员”问题。现在给定了城市数目和在不同城市间旅行所需要的不同费用，那么推销员能否找到一条最为廉价的把所有城市都走遍的线路呢？答案是当然可以，因为我们可以列举出所有的线路，然后挨个比较一番就行了。但是这个方法并不是万能的，三五个城市还好说，但如果是100个城市，那么即便计算机的计算能力达到了每秒10亿亿次，用100的阶乘除以10亿亿次，这种方法也还是需要大约4000个世纪，计算机能算，但推销员他不能等啊。这个问题就不是在“多项式时间”内可以解决的问题，也就是说它不是P问题。

不过，推销员问题虽然不是P问题，但却是NP问题。所谓的NP问题是指，能够在多项式时间内得到确认的一类问题。尽管我们很难找到销售员问题的解，但是要通过计算来确认是否有比给定路线更为廉价的路线，却是非常快捷的。这两者之间的难度差距是十分巨大的，找到销售员问题的解，就好比是在一堆干草中找到一根针，而找到一个比给定路线更为便宜的路线，就好比拿出一根稻草或是那根针，然后问你是否找到了那根针。

可见，任何一个P问题必然也是一个NP问题，因为在多项式时间内找到解，就是对它的确认。而目前亟待解决的问题是，是否任何一个NP问题也都是P问题呢？如果答案是肯定的，那么P=NP就成立了。另一方面，如果我们找到一个NP问题，并且证明不可能存在对于它的高效算法，那么P就不可能等于NP。

这就是流动销售员问题具有重要地位的原因，它本身是一个很难的问题，而且所有其他NP问题都能够转化成它。如果我们能够为这一问题找到一种高效算法，就可以由此而推出P=NP。这个结果就意味着所有的NP问题都能高效地解决。

由此一来，我们便得出了一个推论，那就是我们有可能通过一种高效的计算机算法，找到一个大数的质因数。而现代密码学所依赖的正是这个问题的难度，同时，它还为电子商务的安全性与计算机网络诚信提供了基础。也就是说，如果P=NP，那么黑客与密码窃取者将在计算机世界中更加游刃有余。幸运的是，目前人们认为机器不大可能以高效的方式解决所有的问题，所以至少现在来看，P还不等于NP。