实找不出一个大于2的数字使得方程成立。因此,人们认为这个假设是正确的,但是无法证明它。这个深奥的问题自17世纪提出以来就一直困扰着我们,直到1995年,安德鲁·怀尔斯(Andrew Wiles)完成了一个证明,这个证明过程不仅复杂,而且长篇累牍,费玛的空白边缘肯定是写不下。但是更为重要的是,在证明费玛最后定理的过程中,数学家们证明了其他的、较小的猜想。当这个难解之谜最终被破解时,证明过程里已经牵涉了许许多多新的数学内容7。
证明一个著名的世界难题需要多久,我决定要找出预测这个过程的办法,也就是P对NP问题。考虑到困难程度和重要性,克雷数学研究所(Clay Mathematics Institute)重金悬赏100万美元求解决方法。从本质上来说,我们要判断两类数学问题是否相等。P问题很简单,用今天的计算机就能轻松解决,有时甚至一支铅笔加一张纸就够了。对NP问题来说,验证一个答案的正确性是小菜一碟,但是计算出正确答案可谓比登天还难。也就是说,你根本计算不出一些NP问题的答案,但是很气人,如果我给你一个答案,你会立刻知道它是否是NP问题的正解。
例如,找一个数字的质数因子就是一个NP问题。如果给定一个足够大的数字(比如一个400位长的数字),目前我们认为,只有运用地球上所有的计算资源才有可能求得它的质数因子。即便如此,要确定是哪两个质数相乘得到这个400位长的数字,需要的时间比地球的寿命还要长。
但是,如果我告诉你是哪两个质数,那么你只要简单地一相乘,就知道是不是正确答案了。问题在于,在过去的几十年里人们一直想搞明白,既然NP问题的答案可以很快得到验证(就像验证质数因子,其答案是否也可以很快计算出来?到目前为止,还没有人找到解决棘手的NP难题的捷径,而且似乎NP问题与P问题没有交集,让我们感觉P是不等于NP的。但是,我们可能只是遗漏了一些基本要素,或者欠缺了一些数学技巧,本来它们可以简化这些问题,或者隐含着P等于NP的。这么说吧,判断一个很大的数能否被3整除可有点麻烦,除非你知道下面这个巧妙的方法:如果它的每一个数位上的数字之和能被3整除,那么这个数字就能被3整除。
假设NP问题很困难,这其实是现代密码学背后的基本假设。只要P绝不等于NP,密码的强度就会一直很高。而且,如果P不等于NP,那么许多别的事情会一直难以解决,不论是在大型机构分配资源和物流,还是管理复杂的投资组合,甚至是填字游戏和扫雷游戏。但是,我们并不知道P与NP是否相等。40多年来,我们一直处于不知道的状态。
我们什么时候才能知道呢?可能永远都不会知道。总有一些问题8始终也不能得到解决,而且已经被证明无解。但是也有许多沉寂了数百年的难题,突然有一天,就被一位数学家画上了已证明的句点。这才是解决这个问题的关键。许许多多著名的难题最终得到解决,我意识到,我可以研究这些过程的时间分布规律,然后把规律应用到P对NP这个悬而未决的难题上。如果P对NP问题无异于其他著名的难题,那么也许我可以根据统计数据推算出它要花上多长时间才能得到解决。
因此,虽然我无法确切地预知一个问题何时能得到解决,但是我可以从总体上观察难题,并且发现其内在规律。这样,我们就开始掌控解决难题时的不确定性。
其实如果真的这样做了,我们就会得到一些非常有趣的分布,叫作重尾分布(heavy-tailed distributions)。也就是说:我们无法期望在某一个时点找到解决办法。一些著名的难题过了几十年才得到解决,而另一些位于分布尾部的难题数百年后仍然扑朔迷离。数据集里甚至还有一个著名的猜想(或未经证实的言论),它在1 500年后才最终被证实。
但是通过这个分布,我们就可以知道解决一半的难题需要多少年,你可以取50%这个点,对应出来就是它可能的解决方案时间表。所以,假设难题都是可以解决的,且P对NP问题的发展趋势与其他难题一致,那么我们要等到2024年9,也就是P对NP问题提出的53年后,才会诞生一个解决方案。
这一年仍然会有很多不确定性。但是,现在我们可以通过概率看出数学知识的变化有多快,至少可看出总体的数学知识变化有多快。假定最终我们知道了P是否等于NP,那么我们可以肯定,知识的这种变化将非常迅速,它的发生并不会有太多预兆。
从伊辛模型到概率,数学可以帮助我们了解身边的事实是如何快速变化的。但是,这些相变是特例还是普遍现象呢?我们身边的知识可以缓慢且持续地变化,也可以极为快速地变化,但到底哪一种更有可能呢?
毫无疑问,知识经常是缓慢变化的,然而很多人都有一种直观的感受,那就是我们周遭的知识更新得越来越快,每天都上演着越来越多的快速相变。这种直觉背后是有科学根