互动科普

机器能否按照我们的要求，大量“制造出”足以改变世界的结论？这取决于“P与NP问题”如何解决。很不幸，对于许多NP难题，可能需要数以十亿计的处理器，运算几十亿年才能解决。这似乎成了机器计算乃至于人类知识的极限。

 撰文 约翰·帕夫洛斯（John Pavlus） 翻译 杨扬

1956年3月的一个雪天，在美国普林斯顿大学，一位面目严肃、名叫库尔德·哥德尔（Kurt Gödel）的矮个男人，在给一位重病的朋友写最后一封信。虽然两人在普林斯顿高等研究院已经做了几十年同事，但哥德尔在信件开头，还是非常郑重地写上了约翰·冯诺依曼（John von Neumann）的姓名。他俩都是数学天才，为美国在第二次世界大战后在科学与军事方面取得绝对领导权做出了重要贡献。然而，冯诺依曼患上了癌症，即使是哥德尔这样的天才，除了说一些安慰的客套话，然后换个话题外，也没什么可做的：

对于数学家之外的人来说，哥德尔描述的这个问题非常晦涩难懂（实际上，他可能仅仅是想让冯诺依曼从病情中解脱出来，把注意力转移到这样一个非常专业的讨论上）。他想知道，一个假想的机器需要多长时间才可以给出一个问题的答案。而哥德尔给出的结果听上去就像是科幻小说里的描述：

哥德尔在这里所说的“脑力劳动”，并不是指如同2加2这样最简单的数学计算。他指的是数学家用来开辟新知识领域的直觉灵感。25年前，哥德尔提出的那个如今闻名于世的“不完全性定理”（incompleteness theorems，是指任何无矛盾的公理体系，只要包含初等数论和算术系统，则必定存在一个用这组公理不能判定其真假的命题），已经让数学领域发生了根本性改变。现在他提出的问题是，机器能否按照我们的要求，大量“制造出”足以改变世界的结论？

哥德尔寄出这封信几周之后，冯诺依曼就住进了美国沃尔特·里德陆军医疗中心，在那里不到一年，他就去世了。冯诺依曼生前未能给哥德尔回信。不过，这个问题的生命比这两位数学家更长久。哥德尔提出的问题现在通常被称为“P与NP问题”（P versus NP），已经成为现代计算机科学中的一条组织原则。它已经拓展出一个全新的研究领域——计算复杂度理论（computational complexity theory），这个领域综合了数学、科学和工程学，旨在确定无疑地证明计算机能做什么，以及不能做什么。

但是，“P与NP问题”不仅仅是用塑料和硅，来组成一个我们称之为计算机的新玩意儿。这个问题在物理学、分子生物学、密码学、国家安全、进化、数学发展的极限乃至于真实存在的本质等方面，都有实际意义。从理论上来说，这个问题将确定可计算的范围。而且在21世纪的今天，计算能力的极限看上去越来越像是人类知识本身的极限。

两个数学家的赌约

1975年秋，迈克尔·席普塞（Michael Sipser，现在是美国麻省理工学院数学系主任）还只是美国加利福尼亚大学伯克利分校的一名研究生，不过他知道，很快就会有人解决“P与NP问题”。他甚至认为，自己可能就是解决这一问题的人。当时，席普塞正在和同校计算机科学系的研究生莱昂纳德·阿德勒曼（Leonard Adleman）讨论这个问题。他说，“我深深地迷上了‘P与NP问题’，我有种感觉，我也许能够通过某种和其他人不一样的方法来解决这个问题”。他非常自信，于是他和阿德勒曼打赌：“P与NP问题”即使不能很快得到解决，也一定会在20世纪内被攻克。赌注呢？一盎司（约合31克）纯金。

席普塞和阿德勒曼的赌约令人期待，因为“P与NP问题”本身就是在探讨到底能多么快速地解决其他问题。有时候，只须按部就班地一步一步去做，就可以在经过相对并不太长的步骤之后，很快得到一个结果。就像是在杂货店里买东西一样：你只须按照购物清单，一个一个地打上钩，直到把整个购物清单全都标记完。研究复杂性理论的学者把这些称为“P问题”。这是一个用数学语言来精确描述的名字，P指的是“多项式时间”（polynomial time），意思是说：不管这张购物清单变得多长，要把这张清单上所有东西都打上钩的时间，都不会以一种难以控制的速度增长。

与此不同的是，更多问题不一定能像在清单上逐项打钩那样简单地解决，不过，要检验这些问题的答案是否正确，却很容易。拼图游戏就是个很好的例子：虽然要把它拼好可能需要费些工夫，不过，只要看一眼，你就知道拼得对不对。科学家把这种类似于拼图游戏、很容易检验结果的问题称为“NP问题”。

在席普赛和阿德勒曼打赌的4年前，一位名叫斯蒂芬·库克（Stephen Cook）的数学家已经证明这两类问题是有联系的：每一个可以快速解决的P问题，同时也是一个可以快速验证的NP问题。库克的这一发现引出了“P与NP问题”：上述结论反过来是不是也成立呢？是不是所有可以快速验证的NP问题，同时也是可以快速解决的P问题呢？从那时起，这个问题就一直备受关注。从直观上来看，答案似乎是否定的。判断一个拼图游戏是不是拼好了和想办法把它拼好完全是两回事。换言之，P问题看起来并不等同于NP问题。

可是，令席普塞感到困惑的是，这个看上去非常明确的观点，却没人能从数学上给出证明。而正是由于没有人可以证明这一点，所以仍然存在这样一种可能性：不管看上去多么奇怪，或者多么不可能，所有的NP问题实际上都是P问题伪装的。P问题和NP问题可能是等同的。由于计算机可以很容易地处理任何类型的P问题，所以如果P问题和NP问题确实等同的话，那我们就可以得出结论：计算机解决问题的能力远比我们想象的强大。也许正如哥德尔给冯诺依曼的信中所描述的，只要能通过编程，让机器验证答案是否正确，就可以利用机器有效地解决任何问题。

席普塞知道，这样的结论是不大可能成立的。然而，如果能够证明相反的结论，即P问题并不等同于NP问题（这个结论看上去更有可能成立），也将会具有划时代的意义。

就如同哥德尔的不完全性定理揭示了数学一定包含着某些无法证明的真命题一样，有证据显示，P问题不等同于NP问题这一设想，将揭示出一个与知识极限有关的客观事实。完成一个拼图游戏和确认一个拼图游戏已经拼好是完全不同的两回事，不管我们的计算机有多强大，寻求知识的道路上并没有捷径。

证明一个否定性的结论总是很困难的，但是哥德尔已经做到了这一点。对于席普塞来说，1975年与阿德勒曼打赌时，他还有25年时间去证明他的观点。看上去，时间似乎是绰绰有余的。即使他自己不能证明P问题并不等同于NP问题，也可能会有别人来证明这一点。而且不管是谁给出证明，他都将赢得一盎司黄金的赌注。

计算领域的噩梦

和席普塞一样，阿德勒曼也是看到库克所发表的结果而痴迷上这个问题的，但他并不像席普塞那样对这一问题的解决充满信心。库克的论文是建立在“P问题本身也是NP问题”这个基础之上，同时也证明了确实存在“NP完全问题”（NP-complete）这种特殊的、可以被快速验证的问题。NP完全问题就像是一套魔法钥匙：一旦你找到了某种快速算法，可以解决其中一个问题，那这种算法将同样适用于解决其他所有的NP问题，从而证明P问题等同于NP问题。

可是有一个大麻烦：NP完全问题是计算机科学遇到过的最困难的问题之一。而且NP完全问题的实例一旦被发现，就开始在各个地方涌现。就在库克的论文发表后不久，阿德勒曼在加利福尼亚大学伯克利分校的导师之一——理查德·M·卡普（Richard M. Karp）就发表了一篇里程碑式的研究论文，在文章中卡普指出，21个经典的计算问题无一例外都属于NP完全问题。然后，很快人们就发现了几十个、几百个类似的NP完全问题。阿德勒曼说：“这就像是打开了一座堤坝”。诸如航空运输调度、货物箱装车、数独问题、计算机芯片设计、在结婚宴会上邀请宾客入座、玩俄罗斯方块……数以千计的现实世界中的实际问题，都被证明是NP完全问题。

这把破解“P与NP问题”的诱人钥匙，怎么会看上去似乎特别平常，但同时却又非常难以抓到手呢？现在已经是美国南加利福尼亚大学教授的阿德勒曼说：“这就是我为什么对研究‘P与NP问题’如此感兴趣的原因。这些计算问题的影响力和广度，看上去十分令人敬畏。可是毫无疑问，我们还没有完全搞明白。而且，我们似乎也没办法在很短的时间里搞明白。”阿德勒曼对于“P与NP问题”的悲观态度，引出了一个改变世界的发明：就在他和席普塞订下赌约几年之后，阿德勒曼和同事罗纳德·莱维斯特（Ronald Rivest）、阿迪·沙米尔（Adi Shamir）一起，利用“P问题与NP问题似乎完全不具有可比性”的特点，发明了以他们三人姓氏命名的RSA加密算法。这种算法现在仍然广泛应用于网上银行、通信、国家安全等领域。

NP完全问题，难就难在它们的复杂性会随着问题规模变大而急剧增加。想象一下你是一名背包客，正在规划一次旅行，这趟旅程将经过欧洲很多城市。你想要设计出一条线路，既能经过每一座你想去的城市，同时，走的路程又最短。你要怎样做呢？最简单的方法就是尝试每一种可能的线路。如果要去5座城市，你只须尝试12种可能的线路。如果要去10座城市，可能的线路总数就会激增到超过180 000条。如果要去60座城市，可能的线路总数则会比目前已知的宇宙中所有原子的总数还多。这个计算领域的噩梦就是现在人们所熟知的“旅行商问题”。科学家已经花了超过80年的时间，来努力研究这个问题，可是直到现在，仍然没有人能够找到一种通用的方法，可以比“尝试所有可能性”这种笨方法更好。

这就是NP完全问题不合常理的本质所在，“P与NP问题”也是一样。就算你的计算机拥有的存储器比上帝还多，同时还可以花费宇宙从诞生到灭亡这么长的时间来进行计算，除了某些非常简单的情况之外，几乎所有NP完全问题仍然是不可能解决的。而且，这样的NP完全问题似乎无处不在。实际上，这些NP完全问题不仅仅困扰着计算机科学家，它们同时也“设定”了大自然本身的极限。

自然界的解决方法

荷兰的计算机编程先驱艾兹赫尔·戴克斯特拉（Edsger Dijkstra）明白，计算问题其实已经超出了数学范畴。他曾经说过，“计算机科学并不仅仅和计算机有关，就像天文学并不仅仅和望远镜有关一样”。换句话说，计算是一种由很多系统共同展现出来的行为，这些系统绝不只是由谷歌和英特尔所制造出来的那些。实际上，任何一个依据一系列抽象规则将输入转换为输出的系统，都可以称为计算，包括那些由生物学家和物理学家所开发的系统。

1994年，数学家彼得·肖（Peter Shor）证明：经过巧妙安排的亚原子粒子可以用于破解现代加密算法。2002年，阿德勒曼利用DNA链，找到了一个旅行商问题的最优解。2005年，目前在美国麻省理工学院计算机科学与人工智能实验室的量子计算专家斯科特·阿隆森（Scott Aaronson）利用肥皂泡，有效地计算出了一个“斯坦纳树”问题（Steiner tree，即用线段将平面上的n个点连接起来，并使得这些线段的长度之和最小的最短网络问题）的最优解。这些当然都属于NP问题，计算机只有通过超长时间的计算才有可能解决这些问题。像DNA链、肥皂泡这样的自然系统，是不是有助于解决计算机无能为力的“P与NP问题”呢？

阿隆森回答说：“当然不是。”他的肥皂泡实验，实际上只是间接性地证明了“简单物理系统可以通过某种方式超越P问题和NP问题之间的差别”这一观点。尽管肥皂泡在某些情况下确实“计算”出了最小斯坦纳树问题的最优解，但随着问题规模不断增加，它们很快也会像计算机一样陷入失败。阿德勒曼的DNA链实验也会遇到同样的问题。而肖的量子算法确实可以在所有情况下解决因子分解问题（factoring problem），但几乎可以肯定的是，因子分解问题并不是NP完全问题。因此，肖的算法并没有提供一种可以解决所有NP问题的方法。生物学、经典物理学和量子系统的计算实验，似乎都在支持“解决NP完全问题根本没有捷径”这样一种观点。而如果这一观点成立，那么“P问题并不等同于NP问题”就一定是真命题。

阿隆森接着说道：“当然，我们还不能确定无疑地证明这一点。不过，如果我们不是复杂性理论家，而是物理学家，那对我们来说，‘P问题并不等同于NP问题’这一命题可以说很久之前就已经被证明是自然法则了——就像没有任何物质可以比光速更快这一事实一样。”实际上，一些关于宇宙基本性质的物理理论——比如斯蒂芬·霍金（Stephen Hawking）在研究黑洞时所提出的全息原理（holographic principle）——已经暗示：真实存在本身并不连续，而是由一些离散单元组成的，计算机也是一样（参见《环球科学》2012年第3期《宇宙不是连续的吗》）。因此，看起来十分棘手的NP问题以及它所隐含的知识极限，或许都与宇宙在最基本层面上的机制有关。

足够好的近似解

因此，如果我们这个宇宙本身就受限于“P与NP问题”带来的计算极限，那我们又怎么能期待一次性地全部解决NP完全问题呢？更不用说要想解决某些具体的NP完全问题，可能就要花费万亿年的时间。

举个例子：当人类胎儿在子宫中孕育时，他大脑中数十亿个神经元之间会自行建立连接。这些神经元之间的连接如何才能得到最优化的安排，这是一个NP完全问题——看上去进化已经把这个问题解决了。进化神经生物学家马克·常逸梓（Mark Changizi）说：“当一个神经元从一点延伸出去，与另外一大堆突触点相连接，从本质上说，这就是一个网络优化问题，是NP困难问题的一种。”然而，人类大脑其实并没有完全解决这个问题——它只是给出了一个非常接近最优解的答案。大脑中神经元之间的实际连接，与最优化的安排方式之间的差别不超过3%。就连秀丽隐杆线虫（Caenorhabditis elegans）这样只有302个神经元的蠕虫，即使经过了数十亿代的自然选择，也没能形成一个完美的神经元连接网络。“进化过程确实受限于‘P与NP问题’，”常逸梓说，“但不管怎样，进化在这一问题上所起的作用仍然非常重要，毕竟生命并不总是需要尽善尽美。”

事实证明，计算机也并不总是需要尽善尽美。现代计算机几乎可以做任何有用的事情——更不用说它所实现的许多我们已经认为理所当然的“奇迹”，比如视频游戏机和智能手机之类的发明。这就证明，P问题已经包含了我们的计算需求中相当大的一部分。对于剩下的那些计算需求，不完美的近似算法通常“足够好”，完全可以解决具体问题。实际上，这些“足够好”的算法已经可以解决非常复杂的搜索，或是模式匹配问题。而从技术上来说，这些问题中的大部分都是NP完全问题。虽然从数学角度来看，我们并不总是能够找到这些问题的最优解，但这并不意味着我们得到的答案就一无是处。

以谷歌为例。许多复杂性理论研究人员认为，NP问题本质上就是搜索问题。可是在谷歌公司研发总监皮特·诺尔维格（Peter Norvig）看来，公司需要竭力避免同时处理多个NP问题。诺尔维格说：“我们的用户不求尽善尽美，但求最快完成。”于是，谷歌的研究人员对搜索算法进行优化，计算出结果的速度甚至比解决P问题还快（即在线性时间内就能解决问题），这样几乎瞬间就能得到搜索结果。而如果出现不能用这种方法解决的问题，又该怎么办呢？诺尔维格说：“要么我们会对问题进行重构，使其变得更简单，要么我们就根本不管它。”

这就是“P与NP问题”留给我们的东西，既有丰富的馈赠，也有令人无奈的讽刺。当哥德尔1956年写信给冯诺依曼时，他本来认为，未来解开这个问题之后，将到处都是绝对可靠的推理机器，它们可以替代“数学家的脑力劳动”，只须摁一个按钮，就可以得出新的真理。然而，科学家经过数十年对“P与NP问题”的研究，帮助我们建立起来的却是另一个世界：我们认可了机器计算能力存在极限，并在这一基础上拓展了机器解决问题的能力。谷歌的无人驾驶汽车可以在拉斯韦加斯拥挤的高速公路上自动行驶，IBM的超级计算机“沃森”可以在“危机边缘”（Jeopardy，美国著名的智力竞赛类电视问答节目）中找到取胜之道，这一切都是通过像生命世界中所采用的近似法实现的，而并没有去追求数学上的绝对完美。

100万美元奖金

席普塞打赌时约定的2000年已经过去，他履行承诺，给阿德勒曼寄去了一盎司金子。“我想，阿德勒曼可能希望我把这一盎司金子嵌在有机玻璃的立方体中，这样他就可以放在桌子上，或者别的什么地方，”席普塞说，“不过，我没有那么做。”也正好是在2000年，美国克莱数学研究所宣布，如果有人解决了“P与NP问题”，将得到100万美元的奖金。这让更多人知道了这个问题，不过也吸引了许多业余人士和思维怪人的注意力。席普塞说，如今，他也像许多著名的复杂性理论家一样，会经常收到一些不请自来的电子邮件，请他审阅一些尝试证明“P问题并不等同于NP问题”——或者相反结论的新方法。

尽管“P与NP问题”仍然没有解决，但是许多研究复杂性理论的科学家都坚信，这个问题总有一天会解决。席普塞说：“对于这个问题，我从来没有真正放弃过。”他仍然会不时地拿出铅笔和纸，对这个问题写写算算——这几乎成了他消遣的方式。归根结底，“P与NP问题”本身就是一个NP问题：寻找答案的唯一方法就是继续寻找。或许我们永远也找不到答案，但如果真有答案，我们也只有在看到答案的时候，才知道答案确实存在。