快速计算需要大量内存的理论被推翻：麻省理工学院电气工程与计算机科学教授瑞恩·威廉姆斯（Ryan Williams）发表了一篇题为《用平方根空间模拟时间》的论文，该研究改进了计算机执行计算时的“时间”和“空间”之间关系，推翻了快速计算需要大量内存的传统理念。 在计算机科学中，“时间”是指计算机执行的处理步骤数，“空间”是指计算所需的内存量。上个世纪70年代，研究人员用图灵机理论计算模型证明，当一个计算过程需要 t 步完成时，通过让每个内存单元存储大约 log t 位信息，就可以“压缩”出整个计算所需的空间，只需要大约 t/log t 个内存单元。也就是说，用 O(t/log t) 的空间就可以完成一个时间复杂度为 t 的计算。 威廉姆斯教授的的研究证明，相同的时间 t 计算可以在非常小的空间内进行，只有 O（√（t log t））。比如，想象一下，有一个计算过程，需要经过t步才能完成。传统理论可能认为，你需要大约 t 个“内存单元”来记录这整个过程中的每一步。然而，这项新研究表明，实际上只需要大约 √(t log t) 个页面就足够了！每个内存单元不仅能记下一个简单的标记，而是可以记录大约 log t 个比特的信息。这样，就相当于能把原本需要t个内存单元记录的信息压缩到更少的内存单元里。 新的理论是威廉姆斯教授通过在名为 “Tree Evaluation”（树评估） 的问题中取得的算法改进而实现的。树评估是这样的，一棵树，它的叶子上都有一些初始的数值，而树的内部节点上则挂着各种“运算符”或函数，这些运算符告诉你如何把它们两个子节点的数值合成一个新的数值。树评估问题就是要求按照树的结构，从叶子开始，一步步地计算出每个内部节点的值，最终求出树根的值。利用这种新算法，威廉姆斯教授将复杂的计算转化为更简单的树形结构评估问题，从而显著减少了存储空间。 技术力量认为，这就好比我们有一大堆内容需要记录，直觉上可能需要 t个内存单元进行记录，但是，如果每个内存单元足够精细，就可以容纳更多信息，就可以把所有内容浓缩到只有 √(t log t) 的内存单元中。也就是说，即便计算时间长达 t，所需的存储空间却可以非常小，仅仅是时间 t 的平方根乘上一个对数因子而已。即使计算步骤的数量增加，所需的内存量也明显少于前面的理论。 随着计算规模的增加，这种差异会进一步增加。新理论将有助于解决计算理论中长期未解决的著名的 “P vs. PSPACE” 问题，简单来说，该问题是：所有能在有限空间内解决的问题，是不是也能在有限时间内高效解决？ 它还证明，电路计算可以在内存明显少于之前认为的情况下完成。 信息来源：
