证明了确定性图灵机可在根号时间复杂度的内存中模拟，突破了传统空间瓶颈。
$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
- 通过树高压缩技术，将计算路径重构成深度为对数级的二叉树
- 实现 $O( oot{2}{t})$ 空间复杂度，无额外多对数因子
- 适用于电路复杂度、可验证解释器等场景，适合理论计算机研究者
我们证明了确定性多带图灵机可在 $O( oot{2}{t})$ 空间内模拟 $TIME[t]$ 问题，空间以固定有限字母表的磁带单元计。核心是高度压缩定理：将块尊重运行的典型左深紧凑计算树，统一且在对数空间内重构为二叉树，任意深度优先路径的栈深度为 $O(/log T)$（其中 $T = ceil t/b ceil$），叶子处保持 $O(b)$ 工作空间，内部节点仅需 $O(1)$。边的地址/拓扑可在 $O(/log t)$ 空间验证，合并时语义正确性由唯一接口的精确 $O(b)$ 有界窗口重放保证。算法上采用代数重放引擎、常数次映射、无指针深度优先搜索、无索引流式处理，以及防止叶摘要堆积的滚动边界缓冲，确保每层仅常数大小标记，消除大计数器，获得 $S(b)=O(b + t/b)$ 的加法权衡。取 $b=Θ( oot{2}{t})$ 得 $O( oot{2}{t})$ 空间，无残留多对数因子。构造具统一性、可相对化，对标准模型选择鲁棒。结果包括：大小为 $s$ 有界扇入电路的分支程序上界 $2^{O( oot{2}{s})}$，基于标准层次论证的 $SPACE[n]$-完全问题的紧致二次时间下界，以及 $O( oot{2}{t})$ 空间的可证解释器；在显式局部性假设下，框架可扩展至 $d$ 维几何模型。概念上，该工作将路径管理视为 $O( oot{2}{t})$ 的主要障碍，并通过逐路径分析的结构化高度压缩予以消除，而非依赖屏障技术。
原文摘要 · Abstract (English)
We prove a square-root space simulation for deterministic multitape Turing machines, showing $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ \emph{measured in tape cells over a fixed finite alphabet}. The key step is a Height Compression Theorem that uniformly (and in logspace) reshapes the canonical left-deep succinct computation tree for a block-respecting run into a binary tree whose evaluation-stack depth along any DFS path is $O(\log T)$ for $T=\lceil t/b\rceil$, while preserving $O(b)$ workspace at leaves and $O(1)$ at internal nodes. Edges have \emph{addressing/topology} checkable in $O(\log t)$ space, and \emph{semantic} correctness across merges is witnessed by an exact $O(b)$ bounded-window replay at the unique interface. Algorithmically, an Algebraic Replay Engine with constant-degree maps over a constant-size field, together with pointerless DFS, index-free streaming, and a \emph{rolling boundary buffer that prevents accumulation of leaf summaries}, ensures constant-size per-level tokens and eliminates wide counters, yielding the additive tradeoff $S(b)=O(b+t/b)$. Choosing $b=Θ(\sqrt{t})$ gives $O(\sqrt{t})$ space with no residual multiplicative polylog factors. The construction is uniform, relativizes, and is robust to standard model choices. Consequences include branching-program upper bounds $2^{O(\sqrt{s})}$ for size-$s$ bounded-fan-in circuits, tightened quadratic-time lower bounds for $\mathrm{SPACE}[n]$-complete problems via the standard hierarchy argument, and $O(\sqrt{t})$-space certifying interpreters; under explicit locality assumptions, the framework extends to geometric $d$-dimensional models. Conceptually, the work isolates path bookkeeping as the chief obstruction to $O(\sqrt{t})$ and removes it via structural height compression with per-path analysis rather than barrier-prone techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。