白交 发自 凹非寺
量子位 | 公众号 QbitAI
一个计算机领域的著名问题，在停滞50年之后终于有了进展。
麻省理工学院的威廉姆斯科学家在一次偶然的实验中观察到：证实了存储器的性能实际上比人们所预想的要更为卓越。在众多可设想的计算任务中，即便是有限的存储空间，其价值也等同于大量的时间投入。
时间与存储空间构成了计算领域最为根本的两类资源，任何算法在执行过程中都不可避免地消耗一定的时间，同时还需要占用一定的空间以存放信息。目前，在已知的算法中，所需的空间和运行时间之间呈现出大致的线性关系，研究人员普遍认为，目前尚无更优的解决方案。
目前，威廉姆斯已经证实，有一个数学机制能够将任何算法转换成一种占用空间更小的版本。
由于想法过于不可思议，他当时第一想法是：大概是自己疯了吧
于是他开始努力证明自己的错误，然而经过数小时的深思熟虑，并未发现任何不足之处；或许，说不定，他确实是对的也未可知。
经过数月的精心整理与反复琢磨，成果终于得以发布至网络平台，未曾想，竟赢得了众多网友的一致好评。
华盛顿大学的科研人员指出，这一发现极其令人震惊，同时也标志着一项重大突破。
困扰计算机科学家的半世纪难题
先来看看这是一个什么问题。
用通俗易懂的话来说，这个问题的根源在于我们的一种直观感受：空间是可以被反复利用的，而时间却无法被重复消费。
算法能够多次利用同一片内存空间，然而时间却并不宽容，一旦流逝，便无法再次追回。
但对于正经科学家来说，直觉是不够的，这需要严谨的证明！
哎，这就难到科学家了，没成想一难就难了半世纪。（Doge）
威廉姆斯所在的领域是计算机科学一个分支学科计算复杂性理论
该领域涉及处理诸如列表排序或因式分解等计算任务所需的资源，比如时间和空间。多数问题都能用多种算法来处理，而这些算法在时间和空间上的要求各不相同。复杂性理论研究者会依据最优算法的资源消耗，即运行速度最快或空间占用最少的算法，将问题分类到不同的复杂性类别中。
然而，我们该如何确保计算资源研究在数学层面上达到严谨的标准呢？仅仅对时间与空间进行剖析，这是无法实现的。若想取得实质性的进展，首要任务是准确地进行定义。
在20世纪60年代，计算机领域的专家哈特马尼斯确立了一套精确的定义，这套定义旨在对时间和空间进行深入的分析。
P类包括了所有在合理的时间内能够解决的各类问题。与之相对应，在空间领域，存在一个类似的概念，它被称作“PSPACE”。
这两类问题间的联系构成了复杂性理论的核心议题之一，其中，P类问题无一例外地归属于PSPACE问题范畴，因为即便是最快的算法也无法在有限的时间内耗尽计算机内存中的广阔空间。
若情况相反亦然，则这两类对象彼此间将展现出等同的价值：空间与时间将具备相等的计算效能。
科学家们对PSPACE的分类提出了质疑，他们认为这一类别可能涵盖了比P类更为广泛的范畴，其中包含了许多P类所不具备的问题。换言之，他们相信在计算资源方面，空间的力量可能超越了时间的力量。
为了证实PSPACE的级别高于P，研究者们需证明，在PSPACE范畴内，某些特定问题根本无法通过任何快速算法得到解决。
1965年，哈特马尼斯来到了康奈尔大学，并肩负起新设计算机科学系主任的重任。在他的引领下，该系迅速崛起，成为复杂性理论研究的核心机构。
在20世纪70年代的初期阶段，那两位科研工作者，约翰·霍普克罗夫特与沃尔夫冈·保罗，开始致力于构建时间与空间之间精确的关联。
他们明白，若想攻克 P 与 PSPACE 的问题，关键在于证实某些计算在有限时间内无法完成。然而，这样的证明过程异常艰难。
于是，他们选择从另一个角度来审视这一问题，探究在有限的空间范围内能够实现哪些功能。他们期望证实，在特定的空间资源限制下，算法能够处理与时间资源略微增加的算法所能处理的所有问题。这一发现暗示了空间资源至少在某些方面优于时间资源——这成为了证明 PSPACE 区间大于 P 区间的一个关键且不可或缺的环节。
为了达成这一目标，他们采用了“模拟”策略，这涉及将既有的算法转换成处理同样问题的全新算法，尽管在所需的空间和耗时上存在差异。
有一个常见的例子，你掌握了一种高效的处理方式，能够依照字母顺序对书架上的书籍进行整理，然而这种方法却要求你将书籍分成数十个小组。或许你更倾向于选择一种占用居住空间更小的方案，尽管这样做可能会耗费更多的时间。
模拟本质上是一种数学运算，通过这一过程，你能够获得更为高效的算法。将原始算法输入其中，它将输出一种新的算法方案。这种新算法在节省存储空间方面表现优异，然而，在时间效率上却有所牺牲。
他们意图打造一款通用的模拟软件，该软件适用于各类算法，即便只是略微减少存储空间。到了1975年，在一位名叫瓦利安特的年轻研究员的协助下，他们三人成功地将这一构想付诸实践。
瓦利安特
然而，不久之后，研究陷入了僵局，复杂性理论学者们开始对所面临的可能是根本性的难题产生疑虑。症结所在，正是模拟的普遍适用性和广泛适用性。
然而，在那时，该书的作者保罗以及其合作者迅速证实，普遍适用性实属不易达成。
于是这个问题就这样持续了50年都没有解决。
威廉姆斯是怎么解决的？
1996年，他来到了康奈尔大学，追随哈特马尼斯的脚步。
自大学时期首次遭遇这一难题，他便对其产生了浓厚的兴趣，甚至在计算机科学的专业课程之外，他还选修了逻辑学与哲学的课程，希望从不同的时空角度探寻答案，然而，尽管努力不懈，他却未能找到满意的解决方案。
2010年，在计算记忆领域又取得了一次突破性的进展：那时，人们开始探讨，在极其有限的空间内，哪些问题能够得到有效解决。
2010年，复杂性理论的开拓者Stephen Cook及其同仁提出了一项名为“树评估问题”的挑战。他们证实，若算法的空间限制低于某一特定界限，则无法完成这一任务。然而，这一证明存在瑕疵。它建立在保罗及其团队多年前提出的一个基本假设之上，即算法无法在空间已满的情况下存储新的数据。
过去十余年间，科研人员持续努力修复这一缺陷。到了2023年，Cook之子及其研究同仁成功研发出一项算法，有效解决了树木评估难题，令人惊喜的是，该算法所需的存储空间远低于人们的预期。
老Cook把数据比喻为鹅卵石，这类石头无法被压缩，它们在算法的内存中必须各自占据独特的空间。然而，实验表明，这并非存储数据的唯一途径，我们还可以将这些鹅卵石设想为能够轻微重叠的物体。
威廉姆斯在一堂课上灵光乍现：
深入探究后，我们发现这种模拟技术显著降低了新算法所需的存储空间——其占用空间大致相当于原始算法时间预留量的平方根。
这种创新的节省空间算法运行速度较慢，因此，该模拟在现实中的应用可能性较小。然而，从理论层面来看，它无疑具有划时代的意义。
接着，他仅通过几步数学演算，便逆向证实了时间计算能力的一个负面效应：至少存在某些问题，若不投入超过空间的时间，便无法得到解决。这一更为局限的结论与研究人员事先的预期相吻合。
从定性的角度分析，威廉姆斯的第二个成果给人的感觉，仿佛正是众人长久以来梦寐以求的P与PSPACE问题的解决方案。
两者的区别在于规模。
P和PSPACE属于极其广泛的复杂度范畴，威廉姆斯的研究成果则是在更为细致的层面上进行了探讨。
为了证明PSPACE超越P，研究者需深化两者间的差异。然而，威廉姆斯历经数月努力尝试拓宽这一差距，却屡遭挫折。
半个世纪之前投身于通用模拟领域的瓦利安特研究员，如今正于哈佛大学执教，他坦言：
大二老师曾劝他转方向
尽管如今46岁的他已取得了显著成就，然而回顾往昔，他曾在几十年前遭受过老师的指导转变。
威廉姆斯在阿拉巴马州的乡村度过了他的童年时光，那里坐落着一个占地50英亩的农场。
七岁那年，他首次目睹了电脑的神奇。那时，他的母亲驾车载他穿越县城，前往一个别具一格的学术强化班。他回忆道，当时一款用于制作数字烟花秀的简易程序深深吸引了他——
随机决定一种色彩，随即将其从屏幕中心向任意方位投射出去。你无法预料，最终呈现的将是一幅怎样的画面。
那时起，他对编程产生了极大的热情，即便没有电脑，他也会在纸上编写程序，这让父母感到束手无策。
在高中生涯的最后两年，他转学至阿拉巴马数学与科学学校，这是他首次接触到了计算机科学的理论，并且，这也是他首次明确了自己想要追求的事业方向。
当申请大学之际，他意识到要深入研究复杂性理论，势必要离开故土，然而，他的双亲却坚决地表示，西海岸乃至加拿大都是不可行的。在众多备选方案中，康奈尔大学最终成为了他的首选。
他得以依靠丰厚的经济支持，踏入了这片梦寐以求的土地，那里是理论的摇篮，也是康奈尔大学，这所学术殿堂的起始之地。
然而，进入大二之后，他发现课程内容变得愈发难以掌握。在计算理论这门课程中，他的成绩仅仅达到了中等水平。面对这种情况，老师建议他重新思考，或许可以考虑其他更为适合的职业道路。
他坚决拒绝，选择付出更多努力，选修了一门研究生理论课程，期望在这门更具挑战性的课程中表现出色，以期在研究生申请过程中脱颖而出。
讲授该研究生课程的教师是哈特马尼斯教授，他当时在该领域内享有极高的声望，堪称资深前辈。
威廉姆斯开始每周参加哈特马尼斯开设的办公室课程，他几乎每次都是唯一到场的学生。他的坚持不懈得到了应有的回报：他在课程中取得了优异的成绩，获得了A，并且哈特马尼斯也答应了他，将在下个学期为他提供指导，协助他完成一个独立的研究项目。
在大学时光里，他们二人每周都会定期相聚。哈特马尼斯不断激励他探索一种独具特色的复杂性问题研究途径，同时指导他如何绕开那些无解的困境。
自那时起，他一直致力于复杂性理论的研究。在2010年，他取得了一项具有划时代意义的成就，这一成果被视为在解决P与NP问题上的重要进展。
这一成就进一步确立了威廉姆斯的声望，紧接着，他陆续发表了多篇涉及复杂性理论多个议题的学术论文。
然而，P对PSPACE这一问题始终萦绕在他的心头：他实在想不出什么特别有趣的事物。
这就是真·念念不忘，必有回响吧。
在《量子杂志》的这篇文章中，我们了解到，对于算法而言，少量的记忆胜过大量的时间。研究指出，即便是在计算过程中，存储一些信息也能显著提升效率。这种策略在处理复杂问题时尤为有效，因为它减少了重复计算的需要。因此，算法设计者在追求速度的同时，也不应忽视记忆力的价值。
