计算机理论学习难度逐渐升级

计算机科学理论何时变得如此困难？

不同于理论发展迟缓的局面，目前计算机领域应用面的发展可谓日新月异，比如GPT-3及其衍生的AI模型，各种大数据模型，虽然超大规模云平台等进步不胜枚举，相关成果也举世瞩目，但这些计算机应用发展的实质，都是硬件价格持续快速下跌带来的派生红利，而且，这一现象早在50年前就已为摩尔定律所明确预言，任何可以用算力解决的问题，现在已不再是问题。

然而计算机理论所要解决的问题是非线性的，单纯依赖于硬件堆砌解决不了指数级增长的复杂性，所以计算机理论无法吃到硬件价格快速下跌这波红利，鉴于当前理论发展到了相对枯燥的平台期，这也使得与计算机有关的理论只能向更广更广、更高更复杂，并且很难突破。现在可以说计算机领域就像《三体》中描述的场景，人类的底层科学已经停滞不前，但应用实践却十分繁荣。

Quake3的0x5f3759df是一款应用领域的优秀产品

尽管本文作者并未直接提及，但笔者在此还是想补充一下计算机应用领域的辉煌时刻。和目前流行的算力表概念不同，以前在应用领域，特别是游戏中，各种神秘性的操作层面都不差，像80后的《神雕侠侣》中的“雷神之锤”这样的游戏，肯定会记忆犹新，这种3D游戏能在数十兆内存的环境中飞行，与目前需要数十G容量的所谓3A大作相比，它能在10个G内存，而所谓的3A大作则是如此，但所使用的资源是完全不同的。

Quake3所用的0x5f3759df属于魔法数。这是一种方根倒数速算法，在Quake3模型引擎中引用此法术后，比标准牛顿迭代方法快4倍。

没有人知道《Quake3》的作者Karkak是如何发现这个数字的，估计Karkak自己可能也不知道，因为直到现在的开源版，还有作者自己自己加的“what？“这种注解。

随后，普度大学教授洛蒙特也对这一神奇数字感到好奇，决定好好研究一下卡马克所创造出的这一魔法数究竟是什么神秘。Lomont也是个大神级，经过仔细研究后，他从理论上得出了最佳猜测值0x5f37642f，与卡马克的数字非常接近。

这个故事还没结束呢。Lomont将自己计算的法术值与卡马克数的对比，看谁的数据能得到更快更准确的平方根。但是，卡马克的0x5f3759df精度更高，这让Lomont很生气，最终Lomont被迫被迫离开，为挽回面子，直接用暴力法一数一数试探，最后发现一个数比卡马克数好得多，尽管这两个数字的实际结果非常接近，但是这种暴力的结果是0x5f375a86。

然而，这款0x5f375a86的传奇也许会成为应用领域尊贵的最后一刻，它在硬件性能不断提高，而价格却在下降，程序世界追求的是“大就有”，因为头大玩家拥有的算力往往比普通用户多几千倍，甚至上万倍，所以大厂的精英们基本也没有人再为0x5f37df这种4倍速度的优化费心了。很久以来，应用界都没有出现什么惊天动地、感天动地的神码。

理论上要解决P=NP的问题，只会越来越困难。

尽管线性优化策略不受硬件性能的提高，但指数级的复杂性却不能被忽视，这是不可忽视的。之前有一篇文章介绍了一种SPF最短路径优先的动态规划算法，Dijkstra，在之前的《元宇宙是否会成为IPv6的转折点》中，此问题在地图两点之间求最短路径，相对于时间复杂度可接受的问题，不需穷尽所有可能路线，只需利用贪心加动态规划法，才能求得最优解。

但它衍生出的BRT路线规划，却是一个典型的NP问题，旅行者路线规划要找到一条环线，把地图图中的所有顶点，不要重复走一遍，最后返回到起始点，并且要保证整个路线最短。比方说，假如一位旅行者，要在最短的时间内穿越中国现有23个省、5个自治区、4个直辖市、2个特别行政区，在那些地方，他选择了那些著名景点，总共有34阶乘，这一数字是1000000…(38)。而且，是否能有一种算法，在不逐次迭代所有路径的情况下求得最优解，即P/NP问题，将旅行商路线规划引入到P/NP理论中去解释如下：NP代表所有解的集合也就是10^38次方种走法，并且P代表了其中的一部分，能不能仅仅通过P来解决NP问题，这也被简化为P=NP问题，是否能得到等价的P=NP。

旅行者问题与图论中著名的哈密尔顿回路比较相似，只在边上加权值，而且它们和团问题，顶点覆盖问题等都属于NP完全问题，也就是说只要你解决了其中一个，就等于把剩下的问题也解决了。

以前的因特网规模还不够大，所以所谓的“哈密尔顿图”、旅行商问题等尚未迫切解决，但现在不同了，互联网终端的规模越来越大，特别是随着“元宇宙”这类概念的发展越来越快，我们虽然可以在应用上采用分治策略，将互联网划分为若干自治区(AS)，以尽量避免直接面对NP的难题。但随着GMP(GraphMinorTheorem)等理论的发展几乎完全与P/NP问题联系在一起，P/NP不能移动，计算机理论无法移动。

然而，当P/NP问题如此重要时，人们阿林却没有足够的动力去解决这个问题，根据哥德尔不完备定理，在当前数学研究领域，在NP问题上，一定会存在我们既不能证明也不能证明伪的问题，P对NP问题的解决或许是个完全不值得研究的问题，因为最重要的是，人类可能永远无法获得P对NP问题的解，连这个问题是否真正得到了解答。

短时间内，或规模，靠计算能力，其作用是直接的，但P对于NP问题非常重要，在没有得到明确的答案之前，计算机理论只能发展成所谓的“复杂性”。这个问题实际上回到了先前大家反复讨论的元宇宙哲学问题，人类的最终目标究竟是星辰大海，还是在眼前可以得到的虚拟世界，我们是否会直接在已有的认知基础上开发元宇宙，或者不顾一切地去探索P/NP这一数学难题。