对于算法而言，少量内存胜过大量时间

Quanta Homepage

由 Simons Foundation 支持的编辑独立出版物。

一个计算机科学家的“惊人”证明是 50 年来在计算机科学中最著名的问题之一上的首次进展。

作者： Ben Brubaker 2025 年 5 月 21 日

2024 年 7 月的一个下午，Ryan Williams (opens a new tab) 开始证明自己是错的。距离他偶然发现计算中时间和内存之间关系的惊人发现已经过去了两个月。 这是一个数学证明的粗略草图，表明内存比计算机科学家认为的更强大：少量内存在所有可想象的计算中都像大量时间一样有用。这听起来太不可思议了，以至于他认为肯定有什么地方出错了，于是他立即将证明放在一边，专注于不太疯狂的想法。现在，他终于抽出时间来查找错误。

但事实并非如此。 在花了几个小时仔细研究他的论点后，Williams 找不到任何缺陷。

“我只是认为我疯了，”麻省理工学院的理论计算机科学家 Williams 说。 他第一次开始考虑，也许，也许，内存真的像他的工作所暗示的那样强大。

在接下来的几个月中，他充实了细节，仔细检查了每个步骤，并征求了少数其他研究人员的反馈。 二月份，他最终在网上发布了他的证明 (opens a new tab)，受到了广泛好评。

“太棒了。 它很漂亮，”新泽西州普林斯顿高等研究院的理论计算机科学家 Avi Wigderson (opens a new tab) 说。 Wigderson 一听到这个消息，就给 Williams 发了一封祝贺邮件。 它的主题是：“你让我大吃一惊。”

时间和内存（也称为空间）是计算中两个最基本的资源：每个算法都需要一些时间来运行，并且需要一些空间来存储数据。 到目前为止，已知用于完成某些任务的唯一算法需要与其运行时间大致成比例的空间量，并且研究人员长期以来一直认为没有办法做得更好。 Williams 的证明建立了一个数学程序，用于将任何算法（无论它做什么）转换为使用更少空间的形式。

更重要的是，这个结果——一个关于在给定一定空间量的情况下可以计算什么的陈述——也暗示了第二个结果，关于在一定时间内不能计算什么。 这个第二个结果本身并不令人惊讶：研究人员期望它是真的，但他们不知道如何证明它。 Williams 的解决方案基于他全面的第一个结果，感觉几乎是卡通式的过度，类似于通过为地球上所有其他人建立铁证如山的理由来证明嫌疑谋杀犯有罪。 它也可能提供一种新的方法来解决计算机科学中最古老的未解决问题之一。

华盛顿大学的计算机科学家 Paul Beame (opens a new tab) 说：“这是一个非常惊人的结果，也是一个巨大的进步。” “瑞恩做到这一点有点不足为奇。”

漫游空间

46 岁的 Williams 长着一张开放而富有表现力的脸，头发中带着一丝灰色。 他的办公室俯瞰着麻省理工学院 Stata 中心的彩色尖顶，是创造性利用空间的另一个例子。 一对瑜伽垫将窗台变成了一个临时阅读角，书桌被塞进一个形状奇特的角落，腾出了空间，以便让沙发面向一个摆满数学涂鸦的大白板。

麻省理工学院距离 Williams 在阿拉巴马州农村的童年家园很远，那里并不缺少空间。 他在 50 英亩的农场长大，7 岁时第一次见到电脑，当时他的母亲开车带他穿过县参加一个特殊的学术充实课程。 他回忆起自己被一个简单的程序迷住了，这个程序可以生成一个数字烟花显示器。

“它正在获取一种随机颜色并将其从监视器的中间发送到随机方向，”Williams 说。 “你无法预测你会得到什么样的图片。” 计算机世界似乎是一个狂野而美妙的游乐场，充满了无限的可能性。 年轻的 Williams 被迷住了。

“我正在纸上给自己编写程序，以便在未来的计算机上运行，”他说。 “我的父母真的不知道该如何对待我。”

随着年龄的增长，Williams 从想象中的计算机发展到真正的计算机。 在高中的最后两年，他转到了阿拉巴马州数学与科学学院，这是一所著名的公立寄宿学校，在那里他第一次接触到计算机科学的理论方面。

“我意识到那里有一个更广阔的世界，并且有一种用数学方式思考计算机的方法，”他说。 “这就是我想做的。”

Williams 特别被理论计算机科学的一个分支——计算复杂性理论所吸引。 它涉及解决计算问题（例如对列表进行排序或分解数字）所需的资源（例如时间和空间）。 大多数问题都可以通过许多不同的算法来解决，每种算法都有其自身的时间和空间要求。 复杂性理论家根据解决这些问题的最佳算法的资源需求（即运行最快或使用最少空间的算法）将问题分为几类，称为复杂性类。

但是，如何使计算资源的研究在数学上严谨呢？ 如果您尝试通过比较分钟数和兆字节数来分析时间和空间，您将不会走远。 要取得任何进展，您需要从正确的定义开始。

变得足智多谋

这感觉几乎是卡通式的过度，类似于通过为地球上所有其他人建立铁证如山的理由来证明嫌疑谋杀犯有罪。

这些定义来自 Juris Hartmanis 的工作，他是一位具有有限资源经验的先驱计算机科学家。 他于 1928 年出生于拉脱维亚的一个显赫家庭，但他的童年因第二次世界大战的爆发而中断。 占领的苏维埃军队逮捕并处决了他的父亲，战后 Hartmanis 在一个难民营完成了高中学业。 他进入大学，即使他买不起教科书，他的成绩也很优秀。

他在2009 年的一次采访 (opens a new tab) 中回忆说：“我通过在讲座中做非常详细的笔记来弥补这一点。” “即兴创作和克服困难有一定的优势。” Hartmanis 于 1949 年移民到美国，在堪萨斯城大学学习数学期间，他做了一系列零工——制造农业机械、制造钢铁，甚至担任管家。 他在年轻的理论计算机科学领域取得了辉煌的职业生涯。

1960 年，在纽约州斯克内克塔迪的通用电气研究实验室工作时，Hartmanis 遇到了 Richard Stearns，一位正在做暑期实习的研究生。 在一对开创性的 (opens a new tab) 论文 (opens a new tab) 中，他们为时间和空间建立了精确的数学定义。 这些定义为研究人员提供了比较这两种资源并将问题分类为复杂性类所需的语言。

最重要的类之一使用了谦虚的名称“P”。 粗略地说，它涵盖了所有可以在合理时间内解决的问题。 空间的一个类似复杂性类被称为“PSPACE”。

这两个类之间的关系是复杂性理论的核心问题之一。 P 中的每个问题也在 PSPACE 中，因为快速算法没有足够的时间来填充计算机内存中的大量空间。 如果反向陈述也成立，那么这两个类将是等效的：空间和时间将具有相当的计算能力。 但是复杂性理论家怀疑 PSPACE 是一个更大的类，其中包含许多不在 P 中的问题。换句话说，他们认为空间是一种比时间更强大的计算资源。 这种信念源于算法可以一遍又一遍地使用相同的小块内存，而时间却没有那么宽容——一旦过去，你就无法再获得它。

“直觉是如此简单，”Williams 说。 “你可以重用空间，但你不能重用时间。”

但是直觉对于复杂性理论家来说是不够的：他们想要严格的证明。 为了证明 PSPACE 大于 P，研究人员必须证明对于 PSPACE 中的某些问题，绝对不可能使用快速算法。 他们从哪里开始呢？

太空漫游

碰巧的是，他们从康奈尔大学开始，Hartmanis 于 1965 年搬到那里，担任新成立的计算机科学系主任。 在他的领导下，它迅速成为复杂性理论的研究中心，在 1970 年代初期，那里的两位研究人员 John Hopcroft 和 Wolfgang Paul 开始建立时间和空间之间的精确联系。

我想了想，然后我想，‘好吧，这根本不可能。’ 瑞恩·威廉姆斯

Hopcroft 和 Paul 知道，要解决 P 与 PSPACE 的问题，他们必须证明你不能在有限的时间内进行某些计算。 但是很难证明一个否定。 相反，他们决定将问题颠倒过来，探索在有限空间内可以做什么。 他们希望证明，给定一定空间预算的算法可以解决与具有稍大时间预算的算法相同的所有问题。 这将表明空间至少比时间略微强大——这是表明 PSPACE 大于 P 的一小步但必要的一步。

有了这个目标，他们转向了一种复杂性理论家称为模拟的方法，该方法涉及将现有算法转换为新的算法，这些算法解决相同的问题，但具有不同的空间和时间量。 为了理解基本思想，假设你获得了一个快速的算法来对你的书架进行字母排序，但它要求你将你的书放在几十个小堆中。 你可能更喜欢占用公寓更少空间的方法，即使它需要更长的时间。 模拟是一种数学程序，你可以用它来获得更合适的算法：将原始算法输入其中，它会给你一个新的算法，该算法以牺牲时间为代价来节省空间。

算法设计人员长期以来一直在研究特定任务（如排序）的这些时空权衡。 但是，要建立时间和空间之间的一般关系，Hopcroft 和 Paul 需要更全面的东西：一种通用的节省空间模拟程序，该程序适用于每个算法，无论它解决什么问题。 他们预计这种通用性会带来代价。 通用模拟无法利用任何特定问题的细节，因此它可能无法像专用模拟那样节省空间。 但是，当 Hopcroft 和 Paul 开始他们的工作时，根本没有已知的通用节省空间的方法。 即使节省少量空间也是进步。

突破发生在 1975 年，当时 Hopcroft 和 Paul 与一位名叫 Leslie Valiant (opens a new tab) 的年轻研究人员合作。 这个三人组设计了一个通用模拟程序 (opens a new tab)，该程序总是节省一点空间。 无论你给它什么算法，你都会得到一个等效的算法，其空间预算略小于原始算法的时间预算。

“你可以在这么多时间做任何事情，你也可以在略少的空间内做任何事情，”Valiant 说。 这是连接时间和空间的任务中的第一个重要步骤。

但是，随后进展停滞，复杂性理论家开始怀疑他们遇到了根本障碍。 问题恰恰在于 Hopcroft、Paul 和 Valiant 模拟的通用性。 虽然许多问题可以用比时间少得多的空间来解决，但一些问题直觉上似乎需要几乎与时间一样多的空间。 如果是这样，更节省空间的通用模拟是不可能的。 Paul 和另外两位研究人员很快证明它们确实不可能 (opens a new tab)，前提是你做出一个看似明显的假设：不同的数据块不能同时占用内存中的同一空间。

Wigderson 说：“每个人都理所当然地认为你无法做得更好。”

Paul 的结果表明，要解决 P 与 PSPACE 的问题，需要完全放弃模拟，而采用不同的方法，但没有人有任何好主意。 这就是这个问题停滞了 50 年的原因——直到 Williams 最终打破了僵局。

首先，他必须完成大学学业。

复杂性类

1996 年，Williams 到了申请大学的时候。 他知道追求复杂性理论会带他远离家乡，但他的父母明确表示，西海岸和加拿大是不可能的。 在他剩下的选择中，康奈尔大学因其在他最喜欢的学科的历史上的突出地位而脱颖而出。

他回忆说：“这个人 Hartmanis 定义了时间和空间复杂性类。” “这对我很重要。”

Williams 获得了慷慨的经济援助并被康奈尔大学录取，并于 1997 年秋季入学，计划尽一切努力成为一名复杂性理论家。 他的全神贯注让他的同学印象深刻。

德克萨斯大学奥斯汀分校的计算机科学家 Scott Aaronson (opens a new tab) 说：“他非常非常喜欢复杂性理论。” Aaronson 与 Williams 在康奈尔大学有过交集。

但是到了大二，Williams 在强调数学严谨性而不是直觉的课程中挣扎着跟上进度。 在他在计算理论课程中获得中等成绩后，老师建议他考虑其他职业。 但是 Williams 不会放弃他的梦想。 他加倍努力并参加了一门研究生理论课程，希望在更难的课程中获得优异的成绩会在他的研究生院申请中看起来令人印象深刻。 教授这门研究生课程的是 Hartmanis，当时是该领域的一位老政治家。

Williams 开始每周参加 Hartmanis 的办公时间，在那里他几乎总是唯一出现的学生。 他的坚韧得到了回报：他在课程中获得了 A，Hartmanis 同意在下个学期指导他进行独立研究项目。 在 Williams 在大学期间，他们的每周会议一直在继续。 Hartmanis 鼓励他培养一种个人化的复杂性研究方法，并温和地引导他远离死胡同。

“我当时深受他的影响，”Williams 说。 “我想我现在仍然是。”

如果你获得任何数学成果，这是 50 年来最好的成果，那么你必须做对了什么。 莱斯利·瓦利安特

但是，尽管获得了国家科学基金会的令人垂涎的研究生研究奖学金，但 Williams 还是被他申请的每个博士课程拒绝了。 听到这个消息后，Hartmanis 给一位同事打了电话，然后转过身来祝贺 Williams 被康奈尔大学录取为期一年的硕士课程。 一年后，Williams 再次申请了各种博士课程，并且凭借额外的研究经验，他获得了成功。

Williams 在研究生院和随后的几年里继续从事复杂性理论的研究。 2010 年，在他获得博士学位四年后，他证明了一个里程碑式的成果 (opens a new tab) ——一小步，但却是几十年来最大的一步，朝着解决理论计算机科学中最著名的问题迈进，关于难题的本质。 那个结果巩固了 Williams 的声誉，他继续撰写了数十篇关于复杂性理论中不同主题的其他论文。

P 与 PSPACE 不是其中之一。 自从他在大学第一次遇到这个问题以来，Williams 就一直对它着迷。 他甚至用逻辑和哲学课程补充了他的计算机科学课程，从关于时间和空间的其他角度寻找灵感，但一无所获。

“它一直在我脑海中，”Williams 说。 “我只是想不出任何有趣的东西可以谈论它。”

去年，他终于找到了他一直在等待的机会。

粘糊糊的卵石

Williams 新成果的故事始于在计算中关于内存的不同问题的进展：可以用极有限的空间解决什么问题？ 2010 年，先驱复杂性理论家 Stephen Cook 和他的合作者发明了一项任务，称为树评估问题 (opens a new tab)，他们证明对于空间预算低于特定阈值的任何算法来说，这是不可能的。 但是有一个漏洞。 该证明依赖于 Paul 和他的同事几十年前做出的相同常识性假设：算法不能在已经满的空间中存储新数据。

十多年来，复杂性理论家试图弥补这个漏洞。 然后，在 2023 年，Cook 的儿子 James (opens a new tab) 和一位名叫 Ian Mertz (opens a new tab) 的研究人员将其完全打开，设计了一种算法 (opens a new tab)，该算法使用比任何人想象的少得多的空间解决了树评估问题。 老 Cook 的证明假设数据位就像必须占用算法内存中单独位置的卵石。 但事实证明，这不是存储数据的唯一方法。 “我们实际上可以将这些卵石视为我们可以将它们稍微压在一起的东西，”Beame 说。

Cook 和 Mertz 的算法激起了许多研究人员的好奇心，但不清楚它是否在树评估问题之外有任何应用。 Wigderson 说：“没有人看到它对时间与空间本身有多么重要。”

Ryan Williams 是个例外。 在 2024 年春季，一群学生在他教授的课程中以 Cook 和 Mertz 论文的最终项目为主题做了一个演讲。 他们的热情激励他仔细研究一下。 他一做到这一点，一个想法就跳了出来。 他意识到，Cook 和 Mertz 的方法实际上是一种用于减少空间使用的通用工具。 为什么不使用它来支持连接时间和空间的新通用模拟——就像 Hopcroft、Paul 和 Valiant 设计的那个，但更好呢？

那个经典结果是一种将具有给定时间预算的任何算法转换为具有略小空间预算的新算法的方法。 Williams 看到，基于粘糊糊的卵石的模拟会使新算法的空间使用量小得多——大致等于原始算法时间预算的平方根。 这种新的节省空间算法也会慢得多，因此模拟不太可能具有实际应用。 但从理论的角度来看，它简直是革命性的。

50 年来，研究人员一直认为不可能改进 Hopcroft、Paul 和 Valiant 的通用模拟。 Williams 的想法——如果它奏效——不仅会打破他们的记录——它还会摧毁它。

“我想了想，然后我想，‘好吧，这根本不可能，’”Williams 说。 他把它放在一边，直到那个命运攸关的七月的那一天，他试图找到论证中的缺陷但失败了。 在他意识到没有缺陷后，他花了几个月的时间编写和重写证明，以使其尽可能清晰。

在 2 月底，Williams 终于将完成的论文在线发布 (opens a new tab)。 Cook 和 Mertz 和其他所有人一样感到惊讶。 Mertz 说：“在我做任何其他事情之前，我不得不去散步。”

Valiant 在早上通勤时偷偷预览了 Williams 对他几十年来的成果的改进。 多年来，他一直在哈佛大学任教，就在威廉姆斯在麻省理工学院的办公室的下游。 他们以前见过面，但他们不知道他们住在同一个社区，直到他们在二月下雪天在公共汽车上偶然相遇，当时这个结果还没有公开。 Williams 向震惊的 Valiant 描述了他的证明，并承诺将他的论文发给他。

“我印象非常非常深刻，”Valiant 说。 “如果你获得任何数学成果，这是 50 年来最好的成果，那么你必须做对了什么。”

PSPACE：最后的边疆

通过他的新模拟，Williams 已经证明了关于空间计算结果的积极结果：使用相对较少空间的算法可以解决所有需要更大时间量的问题。 然后，仅仅使用几行数学，他就扭转了这一点，并证明了关于时间计算能力的负面结果：除非你使用比空间更多的时间，否则至少一些问题无法解决。 第二个，更窄的结果与研究人员的预期一致。 奇怪的部分是 Williams 如何到达那里，首先证明一个适用于所有算法的结果，无论它们解决什么问题。

“我仍然很难相信它，”Williams 说。 “这看起来太好了，难以置信。”

用定性术语表达，Williams 的第二个结果可能听起来像是长期寻求的 P 与 PSPACE 问题的解决方案。 区别在于规模。 P 和 PSPACE 是非常广泛的复杂性类，而 Williams 的结果在更精细的级别上起作用。 他建立了空间的力量和时间的力量之间的定量差距，并且为了证明 PSPACE 大于 P，研究人员必须使该差距更大更大。

这是一个艰巨的挑战，类似于用撬棍将人行道裂缝撬开，直到它像大峡谷一样宽。 但可能可以通过重复使用 Williams 模拟程序的修改版本来实现这一点，该程序重复多次关键步骤，每次节省一点空间。 这就像一种反复增加撬棍长度的方法——让它足够大，你就可以撬开任何东西。 这种重复改进不适用于当前版本的算法，但研究人员不知道这是否是根本的限制。

“这可能是一个最终的瓶颈，也可能是一个 50 年的瓶颈，”Valiant 说。 “或者它可能是某人下周可以解决的问题。”

如果这个问题下周解决，Williams 会后悔的。 在他写论文之前，他花了几个月的时间试图扩展他的成果但失败了。 但即使这种扩展是不可能的，Williams 也有信心，更多的空间探索注定会走向有趣的方向——也许会解决一个完全不同的问题。

“我永远无法准确地证明我想证明的东西，”他说。 “但通常，我证明的东西比我想要的要好得多。”

编者注：Scott Aaronson 是 Quanta Magazine_的_顾问委员会的成员。