Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

$TIME[t] \subseteq SPACE[O(\sqrt{t})]$ via Tree Height Compression

Created by
  • Haebom

Author

Logan Nye

Outline

This paper proves a square-root space simulation for a deterministic multi-tape Turing machine, showing that $\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$. The key is the Height Compression Theorem, which reconstructs the standard left-depth compact computation tree for block-respecting execution into a uniform (and log-space) binary tree, maintaining $O(b)$ operations at leaf nodes, $O(1)$ operations at internal nodes, and verifiable edges in log space, while maintaining $O(\log T)$ evaluation stack depth for $T = \lceil t/b \rceil$ along any DFS path. Semantic correctness between merges is proven by exact $O(b)$ window replay on a unique interface. We use midpoint (balanced) recursion, per-path potential to restrict simultaneously active interfaces to $O(\log T)$, and degree constraints to replace multiple merges with balanced binary combiners. Algorithmically, pointerless DFS and indexless streaming, along with an algebraic replay engine that uses constant-order mappings to constant-size fields, guarantee constant-size tokens per level and eliminate wide counters, providing an additive compromise of $S(b)=O(b + \log(t/b))$ for block size $b \ge b_0$, where $b_0 = \Theta(\log t)$, giving $O(\sqrt{t})$ space under the standard choice of $b = \Theta(\sqrt{t})$. The $b_0$ threshold excludes degenerate blocks where scratch addressing dominates the window space. This structure is uniform, relativistic, and robust to standard model choices. The results include a $2^{O(\sqrt{s})}$ branching program upper bound for size-$s$-constrained fan-in circuits, an enhanced quadratic-time lower bound for the $\SPACE[n]$-complete problem via standard hierarchical arguments, and an $O(\sqrt{t})$-space-certified solver. Under explicit locality assumptions, this framework is extended to geometric $d$-dimensional models.

Takeaways, Limitations

Takeaways:
We present a new square root space simulation for a deterministic multi-tape Turing machine ($\TIME[t] \subseteq \SPACE[O(\sqrt{t})]$).
Proof of an upper bound on $2^{O(\sqrt{s})}$ branch programs for size-$s$ constrained fan-in circuits.
Proof of an enhanced second-order lower bound for the $\SPACE[n]$-complete problem.
Suggesting the possibility of developing an $O(\sqrt{t})$-space authentication solver.
Extendibility to geometric $d$-dimensional models (under explicit locality assumptions).
Limitations:
Complexity of proof.
Extension to geometric models is possible only under explicit locality assumptions.
Difficulty in actual implementation.
👍