作量虽然会增加,但这种增加是温和的、线性的,或者是平方级的。
只要给我足够的时间,我一定能完成。
这就是p。
这类问题,只要这就是一套有效的程序,无论数据规模多大,我们的电子计算机都能计算出答案。
但是,这个世界上还有另一类问题。
它们需要所谓的天才灵感。
这就是np。
现在,请各位想像一下。
不是让我去排序卡片,而是让我去破解一个没有密码的保险箱。
或者,让我把那一千张被撕碎的索引卡片,重新拼回一张完整的纸。
如果我运气好到极点,或者说像诸位经常在私下所说的那样,有上帝在我耳边低语。
上帝悄悄告诉了我密码组合,我输入密码,咔嚓一声保险箱就开了。
这时候,验证这个密码是否正確,验证只需一瞬间。
这就是np的核心:验证它是容易的p,但找到它,如果你没有上帝的指引,我们甚至毫无办法。
所以,诸位,这个等式的含义就是:在这个宇宙中,到底有没有一把万能钥匙?
如果p=np,那就意味著,凡是能被迅速检验的,就能被迅速发现。
这意味著拼好一千张碎纸片和给一千张卡片排序一样简单;破解保险箱密码和旋转把手开门一样容易。
这意味著,在座的各位家,你们不需要再去苦思冥想寻找证明路径。
只要这个定理的证明是可以被检验的,那么计算机就能在瞬间替你写出证明过程。
我们假设,围棋的每一步最优解,是那个外星文明通过某种算法计算出来的o
那么,对於我们人类来说,验证一步棋是否是好棋,相对容易。
这是p类问题。
比如,外星人下了一步,我们事后分析,也能看出它的妙处。
但是,寻找这步最优解,对於我们来说,却难如登天。
我们需要在近乎无穷变化中去碰运气。
外星文明通过围棋向我展示了完美的解。
外星文明之所以能碾压我们,只有两种可能。”
林燃竖起第一根手指:“第一,他们的算力已经达到了暴力穷举10的171次方的地步,那就是物理层面的碾压,我们无可奈何。”
他竖起第二根手指:“第二,他们证明了p=np,或者找到了某种接近p=np的近似算法。
他们掌握了通往数学真理的捷径。
他们不需要穷举,他们是通过逻辑的钥匙直接打开了迷宫的大门。
如果是前者,我们是在和上帝下棋。
如果是后者,我们是在和更高维的数学下棋。”
在座对计算机有所了解的,感觉自己看到了上帝,这概念太牛逼了。
(备註:np=p问题发表於1971年,1973年被苏俄科学家独立发现,此时还没有。)
但对计算机不了解的数学家,则感觉自己云里雾里,连问题都听不太懂,哪怕林燃用了很浅显的比喻。
“这就是我请求各位协助的原因。
nasa发起围棋比赛,是筛选人类中直觉最好的大脑,试图用直接去对抗。
而在座的各位,你们的大脑更重要。
nasa需要你们从数学的角度,去思考这个博弈系统的本质。
去思考算法的复杂度,去思考是否存在一种数学结构,可以简化围棋的搜索空间。
如果在座的哪位,能够证明p=np,或者证明p不等於np,那么你对人类文明的贡献,將超越阿波罗登月,超越核武器。
我认为这是最顶级的数学问题。”
台下绝大部分数学家內心都是一个想法:我?你都想不明白让我想明白?这是不是太高看我了,我几斤几两还是很清楚的,我从来没想过自己能去思考最顶级的数学问题。
不少数学家甚至能够感受到在空气中飘荡的巨大嘆息,很多人內心都在嘆息,嘆息自己的智慧不足以解决这个最顶级的数学问题。
林燃並没有停留太久,他推下一块新黑板。
“刚才的比喻是为了让大家在直觉上理解。
现在,我们需要更精確的数学语言来定义这个问题。”
“我们回到图灵机。
这是阿兰·图灵留给我们的遗產,也是我们理解计算本质的基石。
如果你问我,什么是p?”
林燃在黑板上飞快地写下一串公式:“6
..如果我们能找到一种多项式时间的变换函数,把问题a转化为问题b。
那么只要我们能解出b,我们就一定能解出a。
这意味著,问题b至少比a难,或者一样难。
顺著这个逻辑,如果我们把全天下所有的np问题,从逻辑布尔满足性,到哈密顿迴路,到旅行商问题全部进行归约...
“数学告诉我们,必然存在这样一类终极问题。
它是np中最难的问题。
全天下所有的np问题,都可以在多项式时间內转化为它。
我把它命名为np—完全问题...
”
林燃的讲座持续了一下午,在座的数学家们两极分化很严重,有的如痴如醉,有的昏昏欲睡。
反而华国来的数学家代表团,更有代入感一些,他们更能理解图灵机、算法复杂度这些。
因为在华国,哪怕数学家也不是纯粹做数学研究,他们是要参与到生產环节。
像华罗庚提倡的统筹法就广泛运用在生產中。
在这条时间线,数学家们要利用计算机大量介入到生產过程中。
其中他们最常面对的问题就是天气预报算法优化问题,各个地区的优化各不相同,然后设计的算法还要適配计算机,能在计算机上跑,