破解这一数学难题将会使破解者变得富有，但是它对于我们所有人的价值却是无法计算的。如果P=NP，为什么会关系如此重大,《新科学家》杂志为此作出了解释
史蒂芬·库克：P＝NP？问题的提出者
“亲爱的同事们，我很高兴地宣布，我已经证明了P不等同于NP，这一证明用10磅和12磅的字体附在后面”。维奈•德奥拉利卡（VinayDeolalikar），是位于帕洛阿尔托的惠普实验室的一名数学家，从2010年8月开始，他用电子邮件将他的证明发送给一组顶尖计算机科学家。
这是一个爆炸性的声明。德奥拉利卡声称他已经破解了计算机科学领域内的最大难题，这一难题关系到计算机计算的复杂性和基本限制。“P是不是等同于NP？”如果这个问题的答案是肯定的，那么你将会看到世界发生变革，飞机和火车将会准点运行，准确的电子翻译将不再是难事，生命分子的奥秘将会通过点击鼠标而获得解释，但是安全的网络购物将会变得根本不可能。如果上述问题的答案是否定的，正像德奥拉利卡所声称的那样，这将意味着对于一些复杂的问题，由于不能过于简化，以至于使它不能通过计算机精确地加以解决。
千禧年难题
史蒂芬
·库克（Stephen Cook）是加拿大多伦多大学的一名计算机科学家，他于1971年5月首次提出“P是不是等同于NP”问题。他说，“它被证明是一个难的令人难以置信的问题。我从来不认为这个问题的解决将会变得容易，到现在40年已经过去了，它看起来仍和以前一样困难。”
依靠私人资助运行的克雷数学研究所，位于马萨诸塞州剑桥市，2000年，它将“P是不是等同于NP”问题命名为七个“千禧年大奖”难题之一，谁解决了这一问题谁就会获得一百万美元奖金，这一问题的重要性开始被人们强调。从那时开始，库克和这个领域内的其他研究人员就不断收到声称是问题解决方案的电子邮件。荷兰埃因霍温科技大学的格哈德
·沃伊金格（Gerhard Woeginger）甚至将这些解决方案在网络上列成名单，他说,“我们已经见过成百上千种解决方案，我们或多或少可以根据它们证明过程中存在的错误把它们进行分类。”
德奥拉利卡的尝试似乎与前面的尝试有所不同。首先，他来自于一名已经成名的研究人员，而不是希望一夜成名并获得一百万美元奖金的业余“军团”中的一员。另外，库克一开始就对此给了谨慎的肯定。
然而，这一证明最后出错的可能性非常大。有一些研究人员通过在线合作的方式组成了一个非正式团队，他们指出了这一证明中存在的基本错误。马萨诸塞州阿默斯特大学的计算机科学家尼尔
·伊莫恩（Neil Immerman）说，“这一证明很可能不值得吸引那么多人的关注。”尽管德奥拉利卡已经就他们指出的错误中的一些作出了回答，并且在一个学术杂志上发表了一个改进版的解决方案。
现在共同的看法就是德奥拉利卡的证明――像之前所有的尝试一样――是不可靠的，锚点所以，已经困扰人们40年未破解的这一神秘问题仍将继续存在。那么，这一问题究竟是什么？为什么它会如此重要？如果在两个答案中选择一个作为答案又将会导致什么后果？
什么是P？
通常认为，计算机的计算能力是持续不断增长的。每过一两年，我们的数字运算能力大约增加一倍――实际情形总是如此，以至于这一说法被冠以“摩尔定律”的称谓。
当我们谈到限制计算机计算能力的根本因素时，总是倾向于谈论晶体管的数目，或者什么技术或材料可以取代晶体管。而P=NP?问题提出了一个更为基本的限制因素，这一限制因素不在于硬件方面，而在于计算机的机械构造本身。
P=NP不应该被误认为是简单的代数方程――如果这样认为，那么，我们只需要使N等于1，就可以获得克雷数学研究所的百万奖金了。P和NP代表“复杂度类”，也即代表根据问题被计算机解决的难度――问题被分成的种类。
从本质上说，P类问题是指那些相对容易的问题：会存在一种算法，在一个合理的时间内解决它们。试想一下，如果想要看看一个特定的数字是否在列表中出现，一个最简单的解决方法就是运用一个“线性搜索”算法：按顺序逐一检查每个数字，直到你发现你想要的那个。如果这个列表中有n个数字――这是问题的“规模”――那么最多需要n次验证，这种算法就能找到你所要找的数字，所以其运算复杂度与n成正比。这一看法是合理的，这和通过人工计算解决问题具有很大的相似性――例如，通过人工做两个n位数的乘法，大约需要n2次计算才能完成，一个袖珍计算器也将会很容易完成这一工作，只要n是一个相对较小的值。任何复杂度为n的问题，只要n所造成的计算次数在一定的水平（nx）范围内，都可以相对快速地获得解决，这就是说它可以在多项式时间内获得解决，这类问题就被称为P。
什么是NP？
并不是所有的问题都是良性的，在有些情况下，随着问题复杂性的提高，计算时间的增加并不是按照多项式nx的速度增加，而是按照指数xn的速度增加――计算时间增加速度会大幅度提高。试想一下，一个算法要列出从1到n这些数字的所有可能排列，不难想象用什么方法解决这个问题。即使如此，随着n的增加，列举答案所需要的时间也将会急剧增加。即使证明一个问题属于这种非多项式类问题也是非常困难的，因为你必须证明在多项式时间内绝对不存在解决这一问题的算法。
这并不意味着我们不得不放弃那些难以解决的问题。即使一些问题在一个合理的时间内难以获得解决，但通过启发、猜测等方法，仍然可能会使你得到一个答案，而且这一答案的正确性可以轻而易举地得到证明。试想一下一个数独谜题，要找出它的一个解决方案是极其困难的，即使对于一台计算机来说也同样如此，但是只要提供一个已经有答案的谜题，就很容易通过检验这一答案所满足的标准来验证这一答案的有效性。解决方案很难得到但可以在多项式时间内获得证明的问题所构成的复杂度被称为NP，它表示非确定性的多项式时间。
完成一个有效的数独表格，本质上就是在不断地提问这样的问题，“这个数字填在这个格子里合适吗？”对于每一个格子和从1到9的每一个数字，都要一遍又一遍的尝试，直到所有的格子所填写的数字都能够兼容为止。因此，数独问题是一个典型的NP问题，是一个布尔可满足性问题。
下面才是P=NP?问题的要点。所有属于P系列的问题也都属于NP系列：如果你能轻易地找到一个问题的答案，那么也就能很轻易地证明它。但是，反过来是不是成立呢？如果你能轻易地证明一个问题的答案，是不是你就能很轻易地解决它――是不是属于NP系列的每一个问题也都属于P系列？如答案是肯定的，那么这两个系列的问题是一样的：P等同于NP，计算机世界将会发生不可逆转的改变――即使对于初学者来说，通过计算机来解决数独问题也将会是小菜一碟。但是，在我们考虑这些可能性之前，我们必须首先考虑，如果P被证明不等同于NP，那将会发生什么情况？
如果P≠NP将会怎么样？
威廉
·加萨奇（William Gasarch）是马里兰大学学院公园校区的一名计算机科学家，他在2002年向他的一百个同事问了这么一个问题：对于P=NP?这一问题的答案，你是如何认为的？他说，“你可以听人们不假思索地说出他们是如何看待P与NP的关系的，我想把他们的回答记录下来”。P不等同于NP是占压倒性的答案，有61人选择了这一答案，仅仅有9人支持P等同于NP的答案。
如果大多数人的观点被证明是正确的，也就是说P不等同于NP――像德奥拉利卡所揭示的那样――也就是说，是问题由于本身过于复杂以至于使得我们永远没有能力去解决它。如果是这样的话，德奥拉利卡的这一证明对于你或者我来说，在解决NP系列问题上都不会有大的帮助。在P=NP?问题缺少明确答案的情况下，大部分计算机科学家已经假定一些难度大的问题不可能获得精确的解决，他们集中精力设计一些包含近似解决方法的算法，其中的解决方法能够满足大多数实用的目的。沃伊金格说，“我们将会准确地解决问题，就像我们现在正在做的一样。”
如果P被证明不等同于NP，还会产生一些实际的后果。伊默恩说，首先，它将会解释计算机硬件的性能问题，现在计算机通过多个处理器平行运行的方式来分解计算过程，就像许多处理器拥有双核那样，那么它的运行速度也应该是原来的两倍――但是由于某种类型的原因，情况并非如此。“一些东西似乎喜欢它们内在的顺序”，伊默恩说，“一旦我们知道P不等同于NP，我们将会知道其中的原因是什么。”
它也同样会对密码问题产生影响。大多数现代加密技术都建立在这样的假设基础之上――破解出一个数字原先的因数是非常困难的。这对于一个典型的NP问题来说看上去似乎是可能的：要找出304679这一数字的最初因数是困难的，但是很容易就可以证明，这一数字是因数547乘以因数557的积，实时加密使用的密码包含成百上千个数字，但是如果存在解决NP类问题的一个多项式时间内的算法，即使是最复杂的密码也会得以破解。
那么，是不是P≠NP就意味着密码是安全的了呢？并不一定，1995年，加利福尼亚大学圣地亚哥校区的拉塞尔
·因帕利亚佐（Russell Impagliazzo）概括出了关于P=NP?问题争论的五种可能结果，其中四种可能结果都是在坚持P≠NP的情况下，认为许多NP类问题会转变为P类问题。例如，我们可能会发现这样一些问题，即使随着它们自身的发展，其复杂性不断增加，其技术解决的难度也指数倍的增加，但仍然有相对有效的办法来解决它们。如果破解最初的因数问题属于这类问题，密码的安全将会是非常脆弱的。因帕利亚佐说，“证明P不等同于NP并不是我们领域工作的终结，而仅仅是一个开始。”
如果P=NP将会怎么样？
如果P等同于NP，我们的世界将会发生革命。伊默恩说，“世界将会变得疯狂起来”。沃伊金格说，“这将会完全改变我们的生活”。
就像库克在他1971年的开创性论文中证明的那样，这是因为NP类问题存在一个被称为NP完全问题的子集，它们是解决NP难题的关键之所在：找到一种相应算法能够解决NP完全问题，这意味着任何NP问题都可以通过这样的途径在多项式时间内获得解决。
很多现实世界中的问题被认为是NP完全问题，可满足性问题就是一个例子，解决资源最优化配置的背包版本问题和众人皆知的旅行商问题则是其他的例子。这类问题的目的在于找出访问一系列地点最短距离的路线，并返回到出发点，它们是物流以及其他领域一个非常感兴趣的问题。
如果我们能为每一个NP完全问题找到一个多项式时间内的算法，也就将会证明P=NP，那从此以后，所有的NP问题都将会轻而易举地得以解决。这样一个通用的可计算的解决方案的存在，将会使得运输获得完美的调度，实现货物的最高效率配置，并且使得生产的浪费减少到最低限度――这会比我们当前正在应用的勉强能够发挥作用的解决方案要好得多。
这也同样会导致这样一种算法的产生，它几乎可以完美地进行语言识别和语言翻译工作，这将会使得计算机像人一样处理可见信息。伊利诺伊州埃文斯顿西北大学的计算机科学家兰斯
·福特纳（Lance Fortnow）说，“基本上，你可以用计算机来处理你想要完成的任何工作。”另一个奇怪的副作用就是似乎可以宣布数学家是多余的，库克说，“数学问题在很大程度上将会通过计算机来获得解决。”因为要找到一个数学问题的证明是困难的，但是要验证一个问题却是相对容易的，在某种程度上，数学问题本身是一个NP问题，如果P=NP，我们就可以用计算机来获得新的证明。
我们将很快获得答案吗？
不管最后的答案是什么，现在的问题是什么时候我们可以使得这一悬疑问题获得解决？位于马萨诸塞州波士顿的哈佛大学医学院的塞缪尔
·阿博斯曼（Samuel Arbesman）预测，“P=NP?”问题在2024年之前不会获得解决（《新科学家》，2010年12月25日，第24页）。在加萨奇2002年对其同事进行的调查中，仅仅45%的人认为这一问题将会在2050年之前获得解决，他说，“我认为，人们现在更加悲观了，因为这一问题在被列为‘千禧年大奖’难题之一10年后，其研究仍然没有大的进展。”他又补充说，他认为这一问题的证明可能需要长达500年。
其他人则认为这么悲观是多余的，但是他们都承认，当前所面临的任务是非常艰巨的。福特纳说，“当前我们所运用的方法似乎不能使得我们取得进步。”沃伊金格说，“所有简单的想法都不能解决问题，但是我们又不知道到哪儿去找新的办法。”这一问题产生的部分原因还在于研究失败的风险是非常大的，沃伊金格说，“如果你已经拥有了一定的声誉，你就不会再去发表一些使其他人笑话你的研究成果。”
但是，仍然有一些人接受了这一挑战，芝加哥大学的柯坦
·穆尔穆雷（KetanMulmuley）就是其中之一。他拒绝评论他的最近正在接受出版审查的著作，但是一起参与此次研究的同事说他的办法看起来大有希望。从本质上说，这一问题的研究涉及到把P=NP?问题转变成可操作的代数几何问题，代数几何是数学的一个分支，它把图形和方程联系起来。但即使是穆尔穆雷，似乎也没有必要期待一个快速的成功，福特纳说，“他期望这一问题的解决需要整整100年的时间。”
最终，虽然穆尔穆雷采用把P=NP?问题与其他问题相联系的战术，但并没有找到有明显联系的其他问题，数学领域似乎是最有希望的突破口。这一战术在之前就已经得到了应用。1995年，数学家安德鲁·怀尔斯（Andrew Wiles）就曾经把代数几何与数论联系起来，解决了另一个令人瞩目的问题――费马最后定理。“许多解决问题的想法已经存在”，福特纳说，“当一个想法使一个人心智大开的时候，就会完成最后的飞跃。”
沃伊金格同意这样的看法，“这一问题将会被这样一个数学家所解决，他所运用的方法来自于一个完全与此问题没有联系的领域，也就是使用没有人会认为与P=NP?问题有关联的方法。”或许，将要解决P=NP?问题的人已经在他的专业领域内展开了工作，但他仅仅在等待一个时机，把自己的想法和世界上最难的问题的解决联系起来。
资料来源New Scientist
责任编辑 彦 隐
