引用cperciva · 2025-05
“Minus the fuzz: A multitape Turing machine running in time t can be simulated using O(sqrt(t log t)) space (and typically more than t time).”
去掉噱头概述结果:t 时间的多带图灵机可用 O(sqrt(t log t)) 空间模拟
证明时间 t 的多带图灵机可在 O(√(t log t)) 空间内模拟。
论文证明:对所有 t(n) ≥ n,运行时间为 t 的多带图灵机都可以只用 O(√(t log t)) 的空间来模拟,大幅改进了 50 年前 Hopcroft、Paul 和 Valiant 的 O(t/log t) 空间结果。由此可推出大小为 s 的有界扇入电路可在 √s·poly(log s) 空间内求值,并且存在可在 O(n) 空间内解决、却在多带图灵机上需要 n^(2−ε) 时间的显式问题,对 P 与 PSPACE 问题有一点进展。证明把模拟问题归约为一系列隐式定义的树求值(Tree Evaluation)实例,并利用了 Cook 和 Mertz 最近找到的节省空间的树求值算法。
评论者用它概括“多带图灵机的时间 t 可用约 √(t log t) 空间模拟”,并指出作者认为这给出了最坏情形下“以空间换时间”能走多远的上界,且仅限于多带图灵机。
“Minus the fuzz: A multitape Turing machine running in time t can be simulated using O(sqrt(t log t)) space (and typically more than t time).”
“The author of the paper also notes how the result gives an upper bound for how well we can 'trade space for time' in the worst case:”