作者：Ben Brubaker
机器之心编译
相信大家都曾有过这样的经历：运行某个程序时，电脑突然卡住，轻则恢复文件，重则重新创建；或者手机频繁弹出「内存不足」的警告，让我们不得不忍痛删除珍贵的照片或应用。
这些日常的烦恼，其实都指向了计算世界中两个至关重要的基本要素：时间和空间。
时间和空间（也称为内存）是计算中最基本的两种资源：任何算法在执行时都需要一定的时间，并在运行过程中占用一定的空间以存储数据。
以往已知的某些任务的算法，其所需的空间大致与运行时间成正比，研究人员长期以来普遍认为这一点无法改进。
MIT 的理论计算机科学家 Ryan Williams 的最新研究建立了一种数学程序，能够将任意算法 —— 无论其具体执行何种任务 —— 转化为一种占用空间显著更少的形式， 证明少量计算内存（空间）在理论上比大量计算时间更有价值，这颠覆了计算机科学家近 50 年来的认知。
-
论文标题： Simulating Time With Square-Root Space
-
论文地址：https://arxiv.org/pdf/2502.17779
更重要的是，这一结果不仅揭示了在特定空间约束下可执行的计算范围，还间接证明了在有限时间内无法完成的计算类型。虽然后者早已预期它成立，但一直缺乏严格的证明方法。
50 年的探索与瓶颈
Juris Hartmanis
1965 年， Juris Hartmanis 和 Richard Stearns 两人合作发表了两篇开创性论文，首次对「时间」（Time）和「空间」（Space）这两个概念建立了严格的数学定义。
-
论文地址：https://doi.org/10.1090/S0002-9947-1965-0170805-7
这些定义为研究人员提供了一种共同的语言，使他们能够比较这两类资源，并据此将问题划分为不同的复杂性类别（complexity classes）。
其中一个最重要的复杂性类别 P 类，粗略地说，P 类包含所有能够在合理时间内求解的问题。与之对应的一个空间复杂度类别被称为 PSPACE 类 。
这两个类别之间的关系是复杂性理论中的核心问题之一。
所有属于 P 类的问题也都属于 PSPACE 类，这是因为快速算法在运行时通常没有足够的时间使用大量计算机内存空间。反之亦然，即所有 PSPACE 类问题也都能通过快速算法求解，则两个类别将完全等价：计算时间与计算空间在能力上将无本质差异。
然而，复杂性理论研究者普遍认为，PSPACE 类的规模要大得多，其中包含许多不属于 P 类的问题。换言之，他们相信，从计算能力角度来看，空间是一种远比时间更为强大的资源。这种信念源于这样一个事实：算法可以反复使用同一小块内存，而时间却无法重复利用 —— 一旦过去，就无法重来。
然而，复杂性理论家不满足于这种直觉推理：他们需要严谨的数学证明。要证明 PSPACE 类确实严格大于 P 类，研究人员必须能够展示存在某些 PSPACE 内的问题，其本质上不可能被快速算法求解。
1975 年，John Hopcroft、Wolfgang Paul 和 Leslie Valiant 设计了一个通用的「模拟程序」，证明了任何在特定时间内完成的任务，都可以在略少于该时间的空间内完成。这是连接时间和空间的第一个重要步骤，表明空间至少比时间略强。
然而，随后研究进展停滞，复杂性理论学者开始怀疑，他们或许已经碰到了一个根本性的障碍。
问题正出在 Hopcroft、Paul 和 Valiant 所提出的模拟方法的「通用性」特征上。虽然许多问题确实可以在远小于其时间预算的空间内求解，但一些问题从直觉上来看，似乎需要几乎与时间等量的空间。如果这种情况确实存在，那么更高效地节省空间的通用模拟将无从谈起。
不久之后，Paul 与另外两位研究者一道证明了这一点：更高效的通用模拟确实是不可能的，只要采纳一个看似理所当然的前提 —— 不同的数据块在任何时刻不能同时占用同一块内存空间。
Paul 的研究结果表明，若要真正解决 P 与 PSPACE 的关系问题（P versus PSPACE problem），就必须彻底放弃以模拟（simulation）为中心的研究路径，转而寻找一种全新的理论方法。问题在于，当时没人能提出可行的替代方案。
这个研究难题因此陷入僵局，整整持续了五十年 —— 直到 Williams 的工作最终打破了这一僵持局面。
打破僵局
Williams 的新研究源于对另一个计算中内存使用问题的突破性进展：哪些问题可以在极其有限的空间下被解决？
2010 年，复杂性理论先驱 Stephen Cook 与他的合作者设计出一道被称为树评估问题（tree evaluation problem）的新任务，并证明：任何算法若受制于低于某一特定阈值的空间预算，都无法解决这个问题。
然而，这项证明中存在一个漏洞。其推理依赖于 Paul 等人数十年前提出的直觉性假设：算法不能将新数据存入已经被占用的内存空间。
此后超过十年的时间里，复杂性理论研究者一直在尝试弥合这一漏洞。直到 2023 年，Stephen Cook 的儿子 James Cook 与研究者 Ian Mertz 推翻了这一假设。他们设计出一种全新的算法，能够以远低于此前认为的空间开销，解决树评估问题。这一结果使得原有下界证明完全失效。
Cook（左） 与 Mertz（右）
原先 Stephen Cook 的证明假设中，信息位（bit）被视作类似「石子」（pebbles），必须被存放在算法内存中的不同位置。而事实证明，数据的存储方式远比这更为灵活。
Williams 的革命性飞跃
Cook 与 Mertz 提出的算法引起了众多研究者的兴趣，但起初尚不清楚它是否适用于树评估问题（tree evaluation problem）之外的其他场景。
Ryan Williams
2024 年春季，Ryan Williams 任教的一门课中，一组学生将 Cook 和 Mertz 的论文作为期末项目进行展示。学生们的热情激发了他的兴趣，使他决定深入研究这项工作。
一旦着手，他便迅速捕捉到一个关键想法：他意识到，Cook 与 Mertz 提出的方法实质上是一个通用的空间压缩工具。他想到：为何不利用这一工具，设计一种全新的通用模拟机制（universal simulation），以更优的形式链接时间与空间复杂度？就像当年 Hopcroft、Paul 和 Valiant 所构筑的模型，只不过性能更强。
那项经典成果提供了一种方式，可以将任意具有给定时间预算（time budget）的算法，转化为一个空间预算略小的新算法。Williams 则认识到，倘若基于「柔性石子」（squishy pebbles）建立模拟技术，转化后的新算法所需空间将更大幅度降低 —— 大致等于最初时间预算的平方根。
这种新型节省空间的算法运算速度会显著下降，因此不太可能有实际应用。但从理论角度来看，其意义堪称革命性突破。
Williams 的模拟方法从一个已有的概念 ——「块规整图灵机模拟」 (block-respecting Turing machine simulation) 出发并进行了推广。其基本思路是将整个计算过程（假设总共 t 个计算步骤）分解为 t/b 个连续的「计算块」(computation blocks)，每个块包含 b 个计算步骤。
这些「计算块」的输入 / 输出状态（或称为「配置」）之间存在依赖关系，可以形成一个「计算图」 (computation graph)。
Williams 的关键步骤是将这个图灵机在 t 步内的计算问题 —— 特别是判断其最终状态或输出 —— 规约 (reduce) 成一个「树评估问题」 (Tree Evaluation Problem, TEP) 的实例。
这个构造出来的树评估问题实例具有特定的参数：树的高度 h 大致为 t/b（即计算块的数量），每个节点传递的信息的位长度为 b，树的扇入度（每个节点有多少子节点）为 d（一个取决于图灵机本身的小常数）。
重要的是，这棵「树」是「隐式定义」的，意味着不需要在内存中实际构建出整棵树，而是有一套规则可以随时确定树的任何部分应该是什么样子。
对于这个构造出来的「树评估问题」实例，Williams 应用了由 Cook 和 Mertz 提出的算法来求解，Cook-Mertz 算法解决这类树评估问题的空间复杂度大致是 d^(h/2) * poly (b, h) （其中 d 是扇入度，h 是树高，b 是位长）。
Williams 接着分析了总的空间复杂度，并通过精心选择「计算块」的大小 b 来进行优化。当参数 b 被设定为大约 √t (总计算时间 t 的平方根) 时，前面提到的树高 h (约为 t/b) 就变成了大约 √t。
代入 Cook-Mertz 算法的空间复杂度公式（特别是 d^(h/2) 这一项），并综合其他因素（如 log t 因子，来源于对指针、计数器等的记录），最终推导出总的模拟空间复杂度为 O (√t log t)。
（文：机器之心）