{"ID":2880332,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.14831","arxiv_id":"2508.14831","title":"$\\mathrm{TIME}[t]\\subseteq \\mathrm{SPACE}[O(\\sqrt{t})]$ via Tree Height Compression","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.14831","url_pdf":"https://arxiv.org/pdf/2508.14831v4","authors":"[\"Logan Nye\"]","published":"2025-08-20T16:27:53Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.AI\",\"cs.DS\"]","methods":"[]","has_code":false}