您可以仅使用 √f(n) 内存运行任何需要时间 f(n) 的算法。 Ryan Williams 的这篇新论文展示了如何使用更少的内存模拟时间受限的图灵机。 它利用了 STOC 2024 关于树评估的最新研究,将空间需求减少到时间的平方根。
3.36K