对于算法：小块空间比大量时间更有价值

原文：https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/

作者：Ben Brubaker

译者：Kurt Pan

2024年某个七月午后，Ryan Williams 决心证明自己错了。距离他对计算中时间与内存（亦称空间）之间关係的惊人发现已有两个月过去。那是一个数学证明的粗略草图，论证内存比计算机科学家以为的更强大：在所有可想而知的计算中，少量的内存能发挥与大量时间同等的效用。这听来极不可能，因此他认为其中必有错误，于是立刻将该证明搁置，转而专注于不那麽疯狂的想法。如今，他终于抽出时间去找出错误所在。

然而事情并非如此。数小时仔细检查论证后，Williams未能发现任何错漏。

「我当时只觉得自己快要疯了，」Williams说。他是麻省理工学院的一位理论计算机科学家。这是他第一次开始怀疑，也许真的如他的工作所示，内存的威力如此强大。

在接下来的几个月里，他完善细节，审视每一步，并徵求了少数其他研究人员的意见回馈。二月时，他终于将证明发布到线上，并获得广泛赞誉。

• https://arxiv.org/abs/2502.17779

「太了不起了，太优美了，」阿维·维格德森说。他是位于美国新泽西州普林斯顿高等研究院的一名理论计算机科学家。一听到这个消息，维格德森便给Williams发去一封祝贺邮件，主题是：「你震撼了我。」

时间与内存（亦称空间）是计算中两项最基本的资源：每个演算法在运行时都需要耗费时间，并且需要佔用一定空间来存放运行中的数据。迄今为止，完成某些任务的唯一已知演算法，其空间需求约与运行时间成正比，研究人员长期以来都假定不可能做得更优。Williams的证明建立了一种数学程序，能将任何演算法──无论其功能为何──转换为使用空间大幅减少的形式。

更进一步地，这一结果──关于在有限空间下可计算内容的命题──同时蕴含了第二个结果──关于在有限时间内无法计算内容的结论。这第二个结果本身并不令人惊讶：研究人员一直预期它为真，却始终不知道如何证明。Williams的解法基于他那概括性的第一个结果，几乎显得夸张，就如同要证明一名嫌疑犯有罪，却先为地球上其他所有人都建立起坚不可摧的不在场证明。这一方法也可能为攻克计算机科学史上最古老的开放问题之一提供新思路。

「这是一个非常惊人的成果，且意义重大，」华盛顿大学的计算机科学家Paul Beame说。「而这个突破是由Ryan完成的，好像就没那麽惊人了。」

游走于空间之间

46岁的Williams面容开朗，发间已有些许银丝。他的办公室俯瞰麻省理工学院史塔塔中心色彩缤纷的尖顶，亦是巧妙运用空间的示例。两块瑜伽垫将窗臺变成了临时阅读角，书桌被放在一处奇特的转角，腾出空间放置一张面对大型白板的沙发，白板上密密麻麻写满数学符号。

就地理环境而言，麻省理工学院与Williams在阿拉巴马州乡村的童年故居相去甚远，那里空间丰富。他在50英亩的农场长大，七岁那年，母亲开车带他到县城参加特殊学术拔尖班，他才第一次见到电脑。他记得当时被一个简单的数位烟火程式迷住了。

「它会选取随机颜色，从萤幕中央以随机方向散射出来，」Williams说。「你无法预测会看到什麽画面。」于他而言，电脑世界宛如一个充满无限可能的奇幻乐园，从此便深深着迷。

「我会在纸上写下程式，等未来电脑出现时再执行，」他说。「我的父母也不知道该怎麽处置我。」

Williams的办公室，就如同他的最新成果一般，巧妙地运用了空间。

随着年纪增长，Williams从「想像中的电脑」转向真实机器。他高中的最后两年就读于阿拉巴马数学科学学校──一所着名的公立寄宿学校──也是在那里，他首次接触到计算机科学的理论面向。

「我意识到世界上有更广阔的领域，并且可以用数学方式思考电脑，」他说。「这正是我想做的。」

Williams尤其为一门名为计算複杂度理论的分支深深吸引。它研究解决诸如排序列表或质因数分解等计算问题时所需的资源（如时间和空间）。大多数问题都可以被多种演算法解决，每种演算法对时间与空间的需求各不相同。複杂性理论家根据解决这些问题的最佳演算法（即运行最快或佔用空间最少的演算法）对问题进行分类，形成所谓的複杂度类别。

但如何将资源使用的研究以数学方式严谨化？若试图用分钟与兆字节比较时间与空间，便无法取得进展。要有所斩获，首先就得从正确的定义开始。

善用资源

这些定义源自先驱计算机科学家 Juris Hartmanis 的工作，他拥有在资源匮乏条件下解决问题的经验。他于 1928 年出生于拉脱维亚的显赫家族，但童年因第二次世界大战爆发而中断。佔领的苏联军队逮捕并处决了他的父亲，战后 Hartmanis 在难民营完成高中学业。随后他进入大学，虽买不起教科书，却在学业上表现卓越。

「我透过在课堂上做非常详细的笔记来弥补，」他回忆道。「被迫即兴应变、克服困难，其实也有一定优势。」1949 年，Hartmanis 移民美国，一边在堪萨斯城市大学学习数学，一边做各种零工──从农业机械製造到钢铁生产，甚至担任执事──以维持生计。他随后在年轻的理论计算机科学领域开创了辉煌的职业生涯。

1960 年，当他在纽约州申克塔迪的通用电气研究实验室工作时，遇到了暑期实习的研究生 Richard Stearns。两人在两篇开创性论文中，为时间和空间建立了精确的数学定义，为研究人员提供比较这两种资源并将问题分类到複杂度类别的语言工具。

其中最重要的类别之一简称为「P」，大致涵盖所有可在合理时间内解决的问题；与之对应的空间複杂度类别则称为「PSPACE」。

这两个类别之间的关係是计算複杂度理论的核心问题之一。因为快速执行的演算法无法佔满内存，P 中的每个问题自然也属于 PSPACE。如果反向命题也成立，两者便等价，代表空间和时间具备相当的计算能力。但複杂度理论家普遍认为 PSPACE 要大得多，包含许多不属于 P 的问题：换言之，他们相信空间远比时间更强大。这种信念源自演算法可重複使用同一小块内存，而时间一旦流逝就无法取回。

「这种直觉实在太简单，」Williams说。「你可以重複使用空间，但你无法重複使用时间。」

然而，直觉对複杂度理论家而言并不足够：他们需要严谨的证明。要证明 PSPACE 大于 P，研究人员必须展示对某些属于 PSPACE 的问题，快速演算法从根本上不可能存在——他们究竟该从何着手？

事实上，这一切都从康乃尔大学开始。1965 年，Hartmanis 调任该校新成立的计算机科学系主任。在他的领导下，该系迅速成为複杂度理论研究的重镇。1970 年代初，John Hopcroft 和 Wolfgang Paul这两位研究者，便立志要在时间与空间之间建立精确的联繫。

Hopcroft 和 Paul 深知，要解决 P vs PSPACE 问题，必须证明某些计算在有限时间内无法完成。可要证明「做不到」实属艰难。他们遂将问题颠倒：探究在有限空间下能做什麽。他们希望证明，给定一个空间预算的演算法，能解决与稍大时间预算的演算法相同的所有问题。若能如此，便表明空间至少略胜时间──这虽是小步，却是证明 PSPACE 大于 P 的必要开端。

为此，他们转向複杂度理论家称之为「模拟」的方法：将既有演算法转换为在空间与时间消耗上不同但功能等效的新演算法。打个比方：如果你拥有一种快速的书架排序演算法，却要先将书本分成数十小堆摆放，你或许宁可用更省空间、但耗时较长的方法。模拟就是一套数学程序：输入原始演算法，便能输出一个以空间换时间、符合你需求的演算法。

演算法设计者长期研究排序等特定任务的时空折衷，但要确立时间与空间的一般关係，Hopcroft 和 Paul 需要更全面的方案──一套适用于所有演算法的省空间模拟程序，无论其解决何种问题。他们预料，这种通用性势必付出代价：通用模拟无法利用特定问题的细节，省空间的效果不会比专用模拟那麽显着。但在他们着手之时，根本没有人知道任何通用的省空间方法；即便只能省一点空间，也算是进展。

1975 年，Hopcroft 和 Paul 携手年轻研究员Leslie Valiant，取得重大突破。三人提出了一套既通用又能始终省下一点空间的模拟程序。无论输入何种演算法，它都能产生一个等效的新演算法，其空间消耗略低于原演算法的时间预算。

「只要某个问题能在 X 时间内解决，就能在稍少于 X 的空间内完成，」Valiant 如是说。这是连结时间与空间的首个关键里程碑。

然而进展不久便陷入停滞，複杂度理论家开始怀疑已触及某种根本性障碍。阻碍恰在于Hopcroft 、Paul与Valiant模拟的通用性：儘管许多问题确实能以远少于时间的空间解决，但直觉上有些问题似乎需要的空间几乎等同于时间。如果真如此，更省空间的通用模拟就不可能存在。很快，Paul和另外两位研究者证明了这一点：在一个看似显而易见的假设下——不同资料区块不能同时佔用内存体中的同一空间——任何更高效的通用省空间模拟皆不可能。

「大家都认为不可能再做得更好了，」维格德森回忆。

Paul的结果暗示，要解决 P vs PSPACE 问题，就得完全放弃模拟，另寻他路。但没有人提出可行方案。这一僵局持续了五十年，直到莱恩·Williams终于打破了局面。

──但在此之前，他得先完成大学学业。

複杂度类别

1996 年，Williams到了申请大学的时候。他知道要研究複杂度理论，就得离开家乡，但父母明确禁止他申请西岸与加拿大的学校。在剩下的选项中，康乃尔以其在他最爱的学科史上的卓越地位脱颖而出。

「那位Hartmanis定义了时间与空间的複杂度类别，」他当时心想。「这对我很重要。」

Williams以丰厚奖学金获得康乃尔录取，于 1997 年秋季入学，立志不惜一切成为一名複杂度理论家。他的专注令同学印象深刻。

「他对複杂度理论热衷到了极点，」在康乃尔与Williams同期就读、现任德州大学奥斯汀分校计算机科学家的Scott Aaronson说。

可到了二年级，强调数学严谨胜于直觉的课程让Williams难以跟上。一次计算理论课仅得中等成绩后，教授建议他考虑其他发展。他却不肯放弃梦想，毅然再选了研究所理论课，期望在难度更高的课程中取得佳绩，以利申请博士班。教这门课的，就是当时已是学界元老的Hartmanis。

Williams每週都去找Hartmanis的办公时间，而他几乎是唯一出现的学生。他的坚持得到了回报：他在课程中获得了 A，Hartmanis也同意在下学期指导他进行独立研究。这样的师生会面持续了整个大学期间，Hartmanis鼓励他培养个人研究风格，并在必要时温和地引导他避开死胡同。

「当时他对我影响深远，」Williams说。「现在想来，我仍深受其启发。」

儘管获得了国家科学基金会的研究奖学金，Williams却被所有博士班拒绝。Hartmanis得知后立刻打电话给同事，随即转身祝贺Williams取得康乃尔一年制硕士班录取。一年后，凭藉更多研究经验的Williams再次申请博士班，终于获得心仪的青睐。

Williams在研究所及其后的几年里持续鑽研複杂度理论。2010 年，在获得博士学位四年后，他证明了一项里程碑式成果——虽然只是一小步，却是数十年来在解决理论计算机科学最着名的难题（关于困难问题本质）上取得的最大进展。这个成果巩固了Williams的学术声誉，随后他又在複杂度理论的不同领域撰写了数十篇论文。

P vs PSPACE 问题并不在其中。自大学时期首次接触这个问题以来，Williams便对它深感着迷。他甚至在电脑科学课程之外，辅修逻辑与哲学，希望从其他角度获得关于时间与空间的灵感，但始终未有突破。

「这个问题一直萦绕在我脑海深处，」Williams说。「我就是想不出任何足够有趣的点子来讨论它。」

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

可压缩的石子

Williams新成果的故事始于对另一内存问题的进展：究竟哪些问题能在极度有限空间下解决？2010 年，先驱複杂度理论家Stephen Cook与其合作者提出了「树形评估问题」，并证明任何空间预算低于某一临界值的演算法都无法完成此任务。但其中留有一个漏洞──该证明同样基于Paul等人数十年前的常识假设：演算法无法在已满的空间中存放新资料。

十多年来，複杂度理论家致力于填补此漏洞。直到 2023 年，Cook之子James与研究员Ian Mertz一举突破，设计出一种演算法，能以远低于人们预期的空间完成树形评估。原先证明假定资料位元如同石子，必须各占一格；但事实证明，还有其他储存方式。  「我们其实可以将这些石子稍微压扁、堆叠在一处，」比姆说。

Cook and Mertz 的算法激起了许多研究者的好奇，但其应用是否超越树形评估问题并不明朗。Wigderson 说：「没有人看出它对时间对空间问题有多核心。」

Ryan Williams 则是例外。2024 年春季，在他教授的一门课程中，一群学生将 Cook 和 Mertz 的论文作为期末专题报告，他们的热情激发他更深入地审视此论文。他一旦动手研究，灵光一闪：他意识到 Cook 和 Mertz 的方法其实是一种通用的省空间工具。为何不利用它来驱动一个全新的时间—空间通用模拟──像 Hopcroft、Paul 和 Valiant 设计的那种，但更优？

那项经典成果能将任意演算法在给定的时间预算下，转换成空间预算略小的新演算法。Williams 发现，採用「可压缩的石子」模拟，能使新演算法的空间消耗大幅降低──约等于原演算法时间预算的平方根。虽然这样的模拟会让演算法执行速度大幅变慢，难以应用于实务，但从理论角度而言，却堪称革命性。

长达五十年来，研究者皆认为不可能改进 Hopcroft、Paul 和 Valiant 的通用模拟。Williams 的构想──若能成功──不仅仅是打破纪录，而是彻底摧毁它。

「我一开始想，『这根本不可能』，」Williams 说。他先将想法搁置，直到那个命运之日的七月，他尝试找出论证中的破绽却彻底失败。确认毫无破绽后，他又花了数月时间撰写并重写证明，使之儘可能清晰。

二月底，Williams 终于将论文正式上线。Cook 和 Mertz 和其他人一样大感惊讶。Mertz 说：「我必须先出去好好散步，才能做其他事情。」

Valiant 在晨间通勤时，抢先看到了 Williams 对他那数十年成果的改良。他多年来一直在 Harvard University 任教，距离 MIT 的 Williams 办公室咫尺之遥。两人虽曾见过面，却不知住在同一社区，直到某个雪天在公车上偶然相遇，就在成果公开前数週。Williams 向大为惊讶的 Valiant 描述了他的证明，并承诺寄送论文。

Valiant 说：「我非常非常佩服。如果有任何数学成果能在五十年来达到最佳，那一定做对了什麽。」

PSPACE：最后的疆界

使用新模拟，Williams首先证明了空间的计算能力：使用相对较少空间的演算法能解决所有需要稍多时间的问题。接着仅用几行数学，他便颠倒论证，证明时间的计算能力：至少有些问题，除非投入比空间更多的时间，否则无法解决。这第二个、更聚焦的结论，正与研究者的预期相符。最奇特的是Williams如何达成此结果——他先证明了一项适用于所有演算法的普遍性结论，无论它们处理的是何种问题。

「我至今仍难以置信，」Williams说。「这似乎好得不像真实情况。」

Williams利用Cook和Mertz的方法，建立了更强的空间与时间联繫──这是五十年来对该问题的首次实质突破。

再以质性角度而言，Williams的第二个结论或许听来像是P vs PSPACE的终极解答；但关键在于量级。P与PSPACE是极为广泛的複杂度类别，而Williams的结果则在更细微的层次运作。他建立了空间计算威力与时间计算威力之间的量化鸿沟；要进一步证明PSPACE大于P，研究者必须将此鸿沟扩大到更大规模。

这是一项令人生畏的挑战，如同要用撬棍将人行道的裂缝撬宽至大峡谷般宽阔。但或许可透过修改Williams的模拟程序，反复重複关键步骤，每次都节省一点空间——就像不断加长撬棍，够长后就能撬开任何东西。目前的算法版本尚无法实现这种反复改良，但研究者尚不清楚这是否为根本性限制。

「这可能是最终的瓶颈，也可能只是五十年的瓶颈，」Valiant说。「又或者下週就有人能解决它。」

若问题真的在下週获解，Williams恐将懊悔不已。在撰写论文前，他曾花数月尝试延伸成果却皆告失败。但即便这类延伸无法实现，Williams也深信，对空间的更深入探索必将开闢有趣的新方向──或许能在截然不同的问题上取得进展。

「我永远无法精确证明所有我想证明的事，」他说。「但往往，我所证明的，比我原先想要证明的还要好得多。」