使用平方根空间模拟时间

《Journal of the ACM》：Simulating Time with Square-Root Space

对于时间下界t(n)≥n的多带图灵机，提出O(√(t log t))空间模拟方法，优于Hopcroft等人的O(t/log t)空间结果。该模拟证明有界扇出电路可于O(√s poly(log s))空间评估，并存在显式问题在O(n)空间下需n2?ε时间解决，推进P与PSpace界限研究。

　　

摘要

我们证明了对于所有满足条件 $ t(n) \geq n $ 的函数 $ t $，任何在时间 $ t $ 内运行的多带图灵机都可以在仅用 $ O(\sqrt{\log t}) $ 的空间内被模拟出来。这一成果显著改进了霍普克罗夫特（Hopcroft）、保罗（Paul）和瓦利安特（Valiant）在 50 年前（FOCS 1975, JACM 1977）提出的模拟方法，他们的方法在 $ O(t/\log t) $ 的空间内完成了模拟。除此之外，我们的模拟结果还表明：大小为 $ s $ 的有界输入电路可以在 $ O(\sqrt{s} \cdot \text{poly}(\log s)) $ 的空间内对任何输入进行计算；同时，也存在一些显式问题可以在 $ O(n) $ 的空间内得到解决，而这些问题在多带图灵机上需要 $ n^2 - \epsilon $ 的时间来处理（其中 $ \epsilon > 0 $）。这为解决 $ P \text{ vs. } NP $ 这一复杂性问题带来了一些进展。

我们的模拟方法将模拟时间受限的多带图灵机的问题转化为一系列具有良好参数的、隐式定义的树评估（Tree Evaluation）实例，并利用了库克（Cook）和默茨（Mertz）最近发现的、在空间效率方面非常出色的树评估算法（STOC 2024）。