按年被提到
20252025 · 7 次2026
算法与数据结构›经典算法与数据结构·arXiv:2502.17779 · cs.CC

Simulating Time With Square-Root Space

用平方根空间模拟时间
R. Ryan Williams · 2025

证明时间 t 的多带图灵机可在 O(√(t log t)) 空间内模拟。

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 7 人首次 2025-03-26 · 最近 2025-07-15
7不同的人
4活跃月份
7讨论串
6被引(OpenAlex)

论文证明:对所有 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 最近找到的节省空间的树求值算法。

HN 为什么提它

评论者用它概括“多带图灵机的时间 t 可用约 √(t log t) 空间模拟”,并指出作者认为这给出了最坏情形下“以空间换时间”能走多远的上界,且仅限于多带图灵机。

其他难度 5 / 5约 90 分钟经得起时间
读之前最好知道
1图灵机与计算复杂度
2时间与空间复杂度类(P 与 PSPACE)
3树求值问题(Tree Evaluation)
4Hopcroft–Paul–Valiant 模拟

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用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)) 空间模拟
For algorithms, a little memory outweighs a lot of time原评论 ↗
引用LegionMammal978 · 2025-06

“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:”

指出作者说明该结果给出最坏情况下空间换时间的上界,仅适用于多带图灵机
New proof dramatically compresses space needed for computation原评论 ↗
被提交为 story · 5 次