50年僵局打破！MIT最新证明：对于算法少量内存胜过大量时间

AIGC动态13小时前发布 almosthuman2014

74 0 0

文章摘要

计算中的时间和空间是两种最基本的资源，任何算法在执行时都需要一定的时间，并占用一定的空间来存储数据。长期以来，研究人员普遍认为某些任务的算法所需的空间与运行时间成正比，且这一关系无法改进。然而，MIT的理论计算机科学家Ryan Williams的最新研究颠覆了这一认知。他建立了一种数学程序，能够将任意算法转化为占用空间显著更少的形式，证明少量计算内存在理论上比大量计算时间更有价值。这一发现不仅揭示了在特定空间约束下可执行的计算范围，还间接证明了在有限时间内无法完成的计算类型。

复杂性理论的核心问题之一是P类与PSPACE类之间的关系。P类包含所有能够在合理时间内求解的问题，而PSPACE类则包含所有能够在有限空间内求解的问题。尽管所有P类问题都属于PSPACE类，但复杂性理论研究者普遍认为PSPACE类的规模更大，包含许多不属于P类的问题。这种信念源于算法可以反复使用同一小块内存，而时间却无法重复利用。然而，要证明PSPACE类确实严格大于P类，研究人员需要展示存在某些PSPACE内的问题，其本质上不可能被快速算法求解。

1975年，John Hopcroft、Wolfgang Paul和Leslie Valiant设计了一个通用的“模拟程序”，证明了任何在特定时间内完成的任务，都可以在略少于该时间的空间内完成。这是连接时间和空间的第一个重要步骤，表明空间至少比时间略强。然而，随后的研究进展停滞，复杂性理论学者开始怀疑他们或许已经碰到了一个根本性的障碍。Paul的研究结果表明，若要真正解决P与PSPACE的关系问题，就必须彻底放弃以模拟为中心的研究路径，转而寻找一种全新的理论方法。

2010年，复杂性理论先驱Stephen Cook与他的合作者设计出一道被称为树评估问题的新任务，并证明任何算法若受制于低于某一特定阈值的空间预算，都无法解决这个问题。然而，这项证明中存在一个漏洞，其推理依赖于Paul等人数十年前提出的直觉性假设：算法不能将新数据存入已经被占用的内存空间。直到2023年，Stephen Cook的儿子James Cook与研究者Ian Mertz推翻了这一假设，设计出一种全新的算法，能够以远低于此前认为的空间开销，解决树评估问题。

2024年，Ryan Williams受到Cook和Mertz的启发，设计了一种全新的通用模拟机制，以更优的形式链接时间与空间复杂度。他的模拟方法基于“柔性石子”建立模拟技术，转化后的新算法所需空间将更大幅度降低，大致等于最初时间预算的平方根。这种新型节省空间的算法运算速度会显著下降，因此不太可能有实际应用，但从理论角度来看，其意义堪称革命性突破。Williams的模拟方法从一个已有的概念——“块规整图灵机模拟”出发并进行了推广，最终推导出总的模拟空间复杂度为O(√t log t)。