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.

$\Mathrm{TIME}[t]\subseteq \mathrm{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. We show that $\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$, measured in tape cells, over a fixed finite alphabet. The key step is the Height Compression Theorem, which uniformly (and logarithmically) reconstructs the standard left-depth compact computation tree for block-conforming execution into a binary tree such that the evaluation stack depth along any DFS path is $O(\log T)$ for $T=\lceil t/b\rceil$. At the same time, leaf nodes maintain an $O(b)$ workspace and internal nodes an $O(1)$ workspace. Edges have addressing/topology information verifiable in $O(\log t)$ space, and semantic correctness for merging is proven through precise $O(b)$ bounded window replay in a unique interface. Algorithmically, we obtain an additive trade-off of $S(b)=O(b+t/b)$ by guaranteeing constant-size tokens per level via an algebraic replay engine with constant-order mappings to constant-size fields, pointer-less DFS, and index-less streaming, and by eliminating wide counters. Choosing $b=\Theta(\sqrt{t})$ yields an $O(\sqrt{t})$ space with no residual multiplicative polynomial logarithmic factor. This construction is uniform, relativistic, and robust to standard model choices. Consequently, it includes a $2^{O(\sqrt{s})}$ branching program upper bound for size-$s$-constrained fan-in circuits, an enhanced quadratic-time lower bound for $\mathrm{SPACE}[n]$-complete problems via standard hierarchy arguments, and an $O(\sqrt{t})$-space-certified solver. Under explicit locality assumptions, this framework extends to geometric $d$-dimensional models. Conceptually, this study isolates path management as a major obstacle to $O(\sqrt{t})$ and removes it through structural height compression via path-by-path analysis rather than techniques with a high probability of occurrence of obstacles.

Takeaways, Limitations

Takeaways:
We present a new square root space simulation for deterministic multi-tape Turing machines.
Provides improved bounds for branch program upper bounds, quadratic time lower bounds, and space-certified solvers.
Suggesting the possibility of extension with a geometric model.
A novel approach to solving the path management problem with structural height compression is presented.
Limitations:
Further research is needed to determine whether the approach presented in the paper is applicable to all types of algorithms.
Extension to geometric models under explicit locality assumptions requires further research.
👍