半世纪计算机理论僵局被打破！MIT科学家偶然发现：少量内存节省大量计算时间

西风
2025-05-25
13:09:08

来源：量子位

白交 发自 凹非寺

量子位 | 公众号 QbitAI

一个计算机领域的著名问题，在停滞50年之后终于有了进展。

MIT科学家威廉姆斯一次偶然发现：证明内存比大家认为的更强大。在所有可以想象的计算中，少量的内存与大量的时间一样有价值。

时间和内存（空间）是计算中最基本的两种资源，每个算法都需要一些时间来运行，并且在运行时需要一些空间来存储数据。迄今为止，已知的算法里所需的空间与其运行时间基本上都成正比，研究人员认为没有更好的办法。

但现在威廉姆斯证明，存在一个数学程序，可以将任何算法转换成「占用更少空间」的形式。

由于想法过于不可思议，他当时第一想法是：大概是自己疯了吧。

于是开始着手证明自己错了，但想了几个小时也没找出任何瑕疵：没准万一真就自己对了呢。

经过几个月的整理和推敲，最终将成果po到网上，没想到收获大家一种好评。

一华盛顿大学科学家表示：这是一个相当惊人的结果，也是一个巨大的进步。

困扰计算机科学家的半世纪难题

先来看看这是一个什么问题。

如果用大白话来讲，这个问题其实源于我们一种直觉：你可以重复使用空间，但不能重复使用时间。

算法可以反复使用同一小块内存，而时间却不那么宽容，一旦过去，就无法再收回。

但对于正经科学家来说，直觉是不够的，这需要严谨的证明！

哎，这就难到科学家了，没成想一难就难了半世纪。（Doge）

威廉姆斯所在的领域是计算机科学一个分支学科计算复杂性理论。

这个领域就是解决诸如列表排序或因式分解等计算问题所需的资源（例如时间和空间）。大多数问题可以通过多种不同的算法来解决，每种算法对时间和空间都有各自的需求。复杂性理论家根据最佳算法（即运行速度最快或占用空间最少的算法）的资源需求，将问题划分为不同的类别，称为复杂性类别。

但是，如何让计算资源的研究实现数学上的严谨程度呢？如果只是单纯地分析时间和空间，那是不可能的。要想取得进展，首先需要正确的定义。

20世纪60年代，计算机科学家哈特马尼斯建立了用来分析时间和空间的精确定义——

P，涵盖了所有可以在合理时间内解决的问题。空间领域的一个类似复杂性类别被称为“PSPACE”。

这两类问题之间的关系是复杂性理论的核心问题之一。P 中的所有问题也都属于 PSPACE 问题，因为快速算法根本没有足够的时间填满计算机内存中的大量空间。

如果反过来也成立，那么这两个类将是等价的：空间和时间将具有相当的计算能力。

但科学家们怀疑 PSPACE 是一个更大的类，包含许多 P 中没有的问题。换句话说，他们认为空间是一种比时间更强大的计算资源。

为了证明PSPACE大于P，研究人员必须证明，对于PSPACE中的某些问题，快速算法绝对不可能实现。

1965年，哈特马尼斯搬到了康奈尔大学，担任新成立的计算机科学系主任。在他的领导下，该系迅速发展成为复杂性理论的研究中心。

20世纪70年代初，那里的两位研究人员约翰·霍普克罗夫特和沃尔夫冈·保罗着手建立时间和空间之间的精确联系。

他们知道，要解决 P 与 PSPACE 的问题，就必须证明在有限的时间内无法完成某些计算。但要证明这一点却很难。

因此，他们决定反过来思考这个问题，探索有限空间下能做什么。他们希望证明，给定一定空间预算的算法可以解决与时间预算稍长的算法相同的所有问题。这表明空间至少比时间略胜一筹——这是证明 PSPACE 大于 P 的一个小而必要的步骤。

为了实现这一目标，他们转向了一种“模拟”方法，即将现有算法转化为解决相同问题的新算法，但所需的空间和时间有所不同。

有个通俗的例子，你得到了一个快速算法，可以按字母顺序排列书架，但它需要你把书堆成几十个小堆。你可能更喜欢一种占用公寓空间更少的方法，即使它需要更长的时间。

模拟是一种数学过程，你可以用来得到更合适的算法：输入原始算法，它会给出一个新的算法，以节省空间但牺牲时间。

他们俩想要开发一种通用的模拟程序，可以适用于所有算法，哪怕只是节省一点点空间。时间来到1975年， 在一个年轻研究员瓦利安特参与下，他们仨终于把这个想法实现了。

△瓦利安特

但随后进展停滞，复杂性理论家开始怀疑他们遇到了一个根本性的障碍。问题恰恰在于模拟的普适性和通用性。

虽然许多问题可以用比时间少得多的空间来解决，但有些问题直观上似乎需要几乎与时间一样多的空间。

而且当时的作者保罗Paul与合著者也很快证明确实不可能实现普适性。

于是这个问题就这样持续了50年都没有解决。

威廉姆斯是怎么解决的？

1996年，他来到了康奈尔大学，追随哈特马尼斯的脚步。

他自从大学第一次遇到这个问题以来就一直着迷，他甚至在计算机科学课程之外还学习了逻辑学和哲学课程，试图从其他时间和空间视角中寻找灵感，但最终却徒劳无功。

一次转机是在2010年另一个关于计算记忆问题的进展：哪些问题可以用极其有限的空间来解决？

2010 年，复杂性理论先驱 Stephen Cook 和他的同事发明了一项名为“树评估问题”的任务。他们证明了，任何空间预算低于特定阈值的算法都不可能实现这一点。但这其中存在一个bug。该证明依赖于保罗和他的同事几十年前提出的一个常识性假设：算法无法将新数据存储在已满的空间中。

十多年来，科学家们一直试图弥补这一bug。结果在2023年，Cook的儿子和他的工作伙伴，设计了个算法解决了树评估问题，结果发现占用的空间比任何人想象的都要少得多。

老Cook将数据比做鹅卵石，无法挤压，必须在算法的内存中占据不同的位置。但事实证明，这并非存储数据的唯一方式，可以将这些鹅卵石想象成可以稍微挤压在一起的东西。

威廉姆斯在一堂课上灵光乍现：

诶那既然数据可以挤压，这是不是这个方法就相当于是个可以减少空间内存的通用工具了！

经过进一步研究发现，这种模拟可以让新算法的空间占用大大减少——大约等于原始算法时间预算的平方根。

这种新的节省空间的算法也会慢得多，因此该模拟不太可能有实际应用。但从理论角度来看，这无疑是革命性的。

然后，他仅用几行数学运算，就反过来证明了时间计算能力的一个消极结果：至少有一些问题除非使用的时间多于空间，否则无法解决。第二个范围更窄的结果与研究人员的预期一致。

从定性角度来看，威廉姆斯的第二个结果听起来像是人们长期寻求的P与PSPACE问题的解决方案。

两者的区别在于规模。

P和PSPACE是非常广泛的复杂性类别，而威廉姆斯的结果则在更精细的层面上进行。

不要要证明PSPACE大于P，研究人员必须进一步扩大这一差距。但威廉姆斯花了几个月的时间尝试扩展都失败了。

半世纪前参与通用模拟的那个年轻研究员瓦利安特，目前他在哈佛大学任教，他表示

这可能是一个终极瓶颈，也可能是一个持续50年的瓶颈。

又或者下周就可能解决。

大二老师曾劝他转方向

不过现在看46岁的他取得了很大的进展，但几十年前也曾被老师转方向。

威廉姆斯童年住在阿拉巴马州乡村，那里有一个50英亩大的农场。

7岁时第一次见到电脑，当时他的母亲开车带他穿过县城去参加一个特殊的学术强化班。他回忆说，当时一个用于生成数字烟花表演的简单程序让他着迷——

随机选取一种颜色，然后从显示器中央向随机方向发送。「你永远无法预测最终会得到一个什么样的图像」。

这正是那时候开始，他就产生了浓厚的兴趣，没有计算机那就在纸上写程序，父母也不知道拿他怎么办。

高中最后两年，他转学到阿拉巴马数学与科学学校，在那里他第一次接触到计算机科学的理论知识，也第一次确定了想做的事情：

我意识到外面的世界更加广阔，而且有办法用数学的方式思考计算机。

而到了申请大学的时候，他知道攻读复杂性理论需要远离家乡，但他的父母明确表示，西海岸和加拿大是不可能的。在剩下的选择中，康奈尔大学脱颖而出。

于是他凭借丰厚的经济资助，来到了这个梦中情地，这个理论的起始之地康奈尔大学。

不过到了大二，他就很难跟上课程了。他在一门计算理论课上只得到了中等成绩，老师建议他考虑其他职业。

但他不肯，决定加倍努力，修了一门研究生理论课，希望在这门难度更大的课上取得优异的成绩，能让他研究生申请时显得格外突出。

而教授这门研究生课程的教授正是哈特马尼斯，彼时他已是该领域的元老级人物。

威廉姆斯开始每周参加哈特马尼斯的办公室课程，几乎总是唯一到场的学生。他的坚持得到了回报：他在课程中获得了A，哈特马尼斯也同意在下个学期指导他完成一个独立研究项目。

大学期间，他们两个一直保持着每周的会面。哈特马尼斯鼓励他培养一种个性化的复杂性研究方法，并引导他避开死胡同。

在这之后他始终在研究复杂性理论。2010年，他证明了一个里程碑式成果，被认为是朝着P与NP问题解决迈进。

这一成果巩固了威廉姆斯的声誉，他随后又撰写了数十篇关于复杂性理论不同主题的论文。

不过，P 对 PSPACE 这个问题一直在他脑海中挥之不去：我只是想不出什么足够有趣的东西。

这就是真·念念不忘，必有回响吧。

参考链接：
https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/

Read More