1956年3月，在新泽西州普林斯顿的一个雪天，一位身材矮小、外貌像猫头鹰的男子库尔特·哥德尔给一位即将去世的朋友写了最后一封信。哥德尔对约翰·冯·诺伊曼使用了正式的称呼，尽管两人作为普林斯顿高等研究院的同事已经认识了几十年。这两位都是数学天才，在二战后的几年里，为美国科学和军事霸权的建立发挥了重要作用。然而，现在冯·诺伊曼患了癌症，即使像哥德尔这样的天才也无能为力，只能表达一些过于乐观的客套话，然后转移话题
尊敬的冯·诺伊曼先生
我怀着极大的悲痛得知您生病了…… 据我所知，最近几个月您接受了激进的治疗，我很高兴这种治疗如愿以偿地成功了，您现在的身体状况也更好了…….
关于支持科学新闻业
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻业 订阅。通过购买订阅，您将帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事能够继续流传下去。
既然您现在感觉更强壮了，我想斗胆给您写一个数学问题，我很想听听您的意见…….
对于非数学家来说，哥德尔对这个问题的描述完全无法理解。（事实上，他可能只是想通过进行一种高度专业的闲聊来转移冯·诺伊曼对其疾病的注意力。）他想知道假设的机器需要多长时间才能吐出问题的答案。他的结论听起来像是科幻小说里的东西
如果真的有[这样]一台机器……这将具有最重要的意义。也就是说，这显然意味着……数学家关于“是”或“否”问题的脑力劳动可以完全被机器取代.
哥德尔所说的“脑力劳动”并不是指像2加2这样的简单计算。他指的是数学家为了阐明全新的知识领域而进行的直觉飞跃。25年前，哥德尔现在著名的不完备性定理永远地改变了数学。能否制造出一台机器，按需产生类似改变世界的洞见？
在哥德尔寄出信的几周后，冯·诺伊曼住进了华盛顿特区沃尔特·里德陆军医疗中心，不到一年后去世，终生未能回答他朋友的问题。但这个问题比他们两人都活得更久。哥德尔的问题现在被称为P与NP问题，后来成为现代计算机科学的组织原则。它催生了一个全新的研究领域，称为计算复杂性理论——数学、科学和工程学的融合，旨在完全确定地证明计算机在实际条件下能够做什么和不能做什么。
但P与NP问题远不止我们称之为计算机的塑料和硅器件。这个问题对物理学和分子生物学、密码学、国家安全、进化、数学的极限，甚至可能是现实的本质都具有实际意义。这个问题为我们在理论上永远能够计算什么设定了界限。而在21世纪，计算的极限越来越像人类知识本身的极限。
赌注
迈克尔·西普瑟当时只是一个研究生，但他知道会有人很快解决P与NP问题。他甚至认为自己可能是解决问题的人。那是1975年秋天，他正在与加州大学伯克利分校计算机科学系的同班研究生伦纳德·阿德曼讨论这个问题。“我对P与NP问题很着迷，感觉自己能够以一种超越其他人似乎正在接近它的方式来理解它，”西普瑟说，他现在是麻省理工学院数学系主任。他对自己如此有把握，以至于那天与阿德曼打了个赌：P与NP问题将在20世纪末之前解决，甚至更早。赌注的条款是：一盎司纯金。
西普瑟的赌注具有某种诗意的意义，因为P与NP问题本身就是一个关于其他问题可以多快解决的问题。有时，简单地按照步骤清单就能相对快速地达到最终结果。想想去杂货店购物：你逐项勾选清单上的物品，直到到达清单的末尾。复杂性理论家将这些问题标记为P，代表“多项式时间”，这是一种数学上精确的说法，即无论购物清单变得多么长，勾选所有物品所需的时间永远不会以无法控制的速度增长。
相比之下，更多的问题可能实用也可能不实用，无法通过简单地勾选清单上的物品来解决，但检查解决方案很容易。拼图游戏就是一个很好的例子：即使拼图可能需要努力才能完成，你也可以通过查看拼图来识别正确的解决方案。复杂性理论家将这些快速可检查的、“类似拼图游戏”的问题称为NP。
在西普瑟下注的四年前，一位名叫斯蒂芬·库克的数学家证明了这两种问题是相关的：每个快速可解的P问题也是一个快速可检查的NP问题。从库克的洞见中产生的P与NP问题——并且一直困扰着这个领域——询问反过来是否也成立：所有快速可检查的问题也都是快速可解的吗？直观地说，答案似乎是否定的。识别已完成的拼图游戏（“嘿，你拼好了！”）与完成所有工作来找到解决方案是截然不同的。换句话说，P似乎不等于NP。
西普瑟着迷的是，没有人能够用数学证明这个看似显而易见的观察结果。在没有证明的情况下，仍然存在一种可能性，无论多么不可能或奇怪，所有NP问题实际上都可能是伪装的P问题。P和NP可能相等——并且由于计算机可以轻松处理任何P问题，P等于NP将意味着计算机解决问题的能力远远超出我们的想象。它们将完全符合哥德尔在给冯·诺伊曼的信中描述的那样：机械神谕，可以有效地回答几乎任何向它们提出的问题，只要它们可以被编程来验证解决方案。
西普瑟知道这种结果发生的可能性微乎其微。然而，证明相反的、更可能发生的情况——P不等于NP——同样具有开创性。
就像哥德尔的不完备性定理揭示了数学必须包含真实但无法证明的命题一样，证明P不等于NP将揭示一个关于知识局限性的客观真理。拼图游戏和识别出拼图已完成是两件根本不同的事情，无论我们的计算机变得多么强大，获得知识都没有捷径。
证明否定总是很困难，但哥德尔做到了。因此，对于西普瑟来说，与阿德曼打赌时，25年似乎有足够的时间来完成这项工作。如果他自己无法证明P不等于NP，其他人也会证明。而他仍然会多得一盎司黄金。
快速变得复杂
阿德曼与西普瑟一样对这个问题着迷，即使不像西普瑟那样有信心，因为有一个神秘的数学线索。库克的论文证明了P问题都是NP问题，同时也证明了一种特殊类型的快速可检查问题——NP完全问题的存在。这些问题就像一套神奇的钥匙：如果你找到一种快速算法来解决其中一个问题，那么该算法也将解锁所有其他NP问题的解决方案，并证明P等于NP。
只有一个问题：NP完全问题是计算机科学领域任何人见过的最难的问题之一。一旦被发现，它们就开始无处不在。在库克的论文发表后不久，阿德曼在伯克利的导师之一理查德·M·卡普发表了一项里程碑式的研究，表明21个经典的计算问题都是NP完全问题。几十个，然后是数百个，很快就随之而来。“这就像从堤坝上拔出一根手指，”阿德曼说。安排航空旅行、将搬家箱子装进卡车、解决数独谜题、设计计算机芯片、安排婚礼招待会的客人座位、玩俄罗斯方块以及数千个其他实际的、现实世界的问题都被证明是NP完全问题。
这个解决P与NP问题的诱人钥匙怎么会同时显得如此普遍又如此难以破解呢？“这就是为什么我对研究P与NP问题感兴趣，”阿德曼说，他现在是南加州大学的教授。“这些计算问题的力量和广度似乎非常令人敬畏。但我们当然不理解它们。而且似乎我们也不会很快理解它们。”（阿德曼对P与NP问题的悲观态度导致了一项改变世界的发明：在下注几年后，阿德曼和他的同事罗纳德·李维斯特和阿迪·萨莫尔利用P和NP看似不可通约的性质，创建了他们同名的RSA加密算法，该算法仍然广泛用于网上银行、通信和国家安全应用。）
NP完全问题之所以困难，是因为它们快速变得复杂。想象一下，你是一个背包客，计划穿越欧洲的多个城市旅行，你想要一条路线，让你能够穿过每个城市，同时最大限度地减少你需要旅行的总距离。你如何找到最佳路线？最简单的方法是尝试每一种可能性。如果有五个城市要游览，你只需要检查12条可能的路线。如果有10个城市，可能的路线数量就会激增到超过18万条。如果有60个城市，路径的数量将超过已知宇宙中原子的数量。这种计算噩梦被称为旅行商问题，在80多年的深入研究中，没有人找到一种通用的解决方法，可以比逐一尝试每一种可能性更好。
这就是NP完全问题——以及P与NP问题的悖论本质：不仅所有NP完全问题都同样不可能解决，除非在最简单的情况下——即使你的计算机拥有比上帝更多的内存和整个宇宙的生命周期来工作——它们似乎也无处不在。事实上，这些NP完全问题不仅仅让计算机科学家感到沮丧。它们似乎限制了自然本身的能力。
自然的密码
先锋荷兰程序员艾兹格·迪科斯彻明白，计算问题具有超越数学的意义。他曾经说过，“计算机科学与计算机的关系，就像天文学与望远镜的关系一样。”换句话说，计算是一种行为，除了谷歌和英特尔制造的系统外，许多系统都表现出这种行为。事实上，任何通过一组离散规则将输入转换为输出的系统——包括生物学家和物理学家研究的系统——都可以说是正在进行计算。
1994年，数学家彼得·秀尔证明，巧妙排列的亚原子粒子可以破解现代加密方案。2002年，阿德曼使用DNA链找到了旅行商问题实例的最佳解决方案。2005年，量子计算专家斯科特·阿伦森（Scott Aaronson）使用肥皂泡有效地计算出了一个被称为斯坦纳树的问题的最佳解决方案。这些都是典型的NP问题，计算机应该会因此烧毁电路板。这些自然系统是否知道一些计算机不知道的关于P与NP问题的东西？
“当然不是，”阿伦森说。他的肥皂泡实验实际上是对简单物理系统可以某种程度上超越P和NP问题之间差异的说法的反证法。虽然肥皂泡确实在少数情况下“计算”出了最小斯坦纳树的完美解决方案，但随着问题规模的增加，它们很快就失败了，就像计算机一样。阿德曼的DNA链实验也碰到了同样的墙。秀尔的量子算法在所有情况下都有效，但它破解的因式分解问题几乎肯定不是NP完全问题。因此，该算法没有提供解锁所有其他NP问题的钥匙。生物学、经典物理学和量子系统似乎都支持NP完全问题没有捷径的观点。而这只有在P不等于NP的情况下才是正确的。
“当然，我们仍然无法用确凿的证据来证明这一点，”阿伦森说。“但是，如果我们是物理学家而不是复杂性理论家，‘P不等于NP’早就被宣布为自然法则了——就像没有什么东西可以比光速更快一样。”事实上，一些关于宇宙基本性质的物理理论——例如斯蒂芬·霍金关于黑洞的研究提出的全息原理——暗示现实的结构本身不是连续的，而是由离散的比特组成的，就像计算机一样[参见迈克尔·莫耶的文章“空间是数字化的吗？”；《大众科学》，二月]。因此，NP问题的明显难解性——以及由此暗示的知识局限性——可能从最基本的层面上就根植于宇宙之中。
大脑机器
因此，如果宇宙本身都受到P与NP问题施加的计算限制的约束，那么NP完全问题怎么会似乎总是得到解决呢——即使在某些情况下，找到这些解决方案应该花费数万亿年以上的时间？
例如，当人类胎儿在子宫中发育时，它的大脑会由数十亿个独立的神经元自行连接起来。找到这些细胞的最佳排列方式是一个NP完全问题——进化似乎已经解决了这个问题。“当一个神经元从一个点延伸出来到达一大堆其他突触点时，这基本上是一个图优化问题，这是一个NP难题，”进化神经生物学家马克·张吉说。然而，大脑实际上并没有解决这个问题——它只是做了一个近似的解。（在实践中，神经元始终在最佳排列方式的3%以内。）即使是只有302个神经元的秀丽隐杆线虫，也没有完美的神经线路图，尽管数十亿代的自然选择作用于这个问题。“进化受到P与NP问题的约束，”张吉说，“但它仍然有效，因为生命并不总是需要完美才能良好地发挥作用。”
事实证明，计算机也是如此。现代计算机能够做任何有用的事情——更不用说在我们所有人都认为理所当然的视频游戏机和智能手机上实现奇迹般的壮举——这证明了P问题包含了我们的大量计算需求。对于其余的问题，通常一个不完美的近似算法就足够了。事实上，这些“足够好”的算法可以解决极其复杂的搜索和模式匹配问题，其中许多问题在技术上是NP完全问题。这些解决方案并不总是数学上在每种情况下都是最优的，但这并不意味着它们没有用。
以谷歌为例。许多复杂性研究人员认为NP问题本质上是搜索问题。但据谷歌的研究主管彼得·诺维格称，该公司煞费苦心地避免处理NP问题。“我们的用户更关心速度而不是完美，”他说。相反，谷歌的研究人员针对比P（称为线性时间）更快的计算复杂性类别优化他们的算法，以便搜索结果几乎立即出现。如果出现无法以这种方式解决的问题呢？“我们要么重新构建问题使其更容易解决，要么就不理会它，”诺维格说。
这就是P与NP问题的遗产和讽刺之处。1956年，哥德尔在给冯·诺伊曼的信中认为，这个问题预示着一个充满绝对可靠的推理机器的未来，这些机器能够取代“数学家的脑力劳动”，并通过按下按钮就能产生大胆的新真理。相反，数十年来对P与NP问题的研究帮助构建了一个世界，在这个世界中，我们通过接受机器的局限性来扩展机器解决问题的能力。逼真的近似，而不是机械的完美，是谷歌的自动驾驶汽车如何在拥挤的拉斯维加斯高速公路上自动驾驶，以及IBM的沃森如何在《危险边缘》节目中猜谜获胜的原因。
淘金热
2000年过去了，西普瑟给阿德曼寄去了一盎司黄金。“我想他希望把它镶嵌在一个有机玻璃立方体中，这样他就可以把它放在他的办公桌上或其他地方，”西普瑟说。“我没有那样做。”同年，马萨诸塞州剑桥市的克雷数学研究所为解决P与NP问题提供了新的赏金：100万美元。这笔奖金有助于提高这个问题的影响力，但也吸引了业余爱好者和怪人的注意；如今，像许多著名的复杂性理论家一样，西普瑟说，他经常收到主动发来的电子邮件，要求他审查一些证明P不等于NP的新尝试——或者更糟糕的是，相反的尝试。
尽管P与NP问题仍然未解决，但许多复杂性研究人员仍然认为它有一天会得到解决。“我从来没有真正放弃它，”西普瑟说。他声称自己仍然时不时地拿出纸笔来研究它——几乎是为了消遣，就像狗啃它最喜欢的骨头一样。毕竟，P与NP问题本身就是一个NP问题：找到答案的唯一方法就是不断搜索。虽然这个答案可能永远不会出现，但如果出现，当我们看到它时就会知道。