Simulating Time With Square-Root Space¹¹1To appear in STOC 2025.

Section 2 discusses preliminaries (which we do not recommend skipping, but it is short). Section 3 begins by proving a short “warm-up” simulation (Theorem 3.1) which already achieves $O(\sqrt{t}\log t)$ space and gives many of the key ideas. Section 3.2 proves Theorem 1.1, discusses the possibility of improvement, and proves Theorem 1.5. Section 4 discusses various corollaries mentioned earlier, and Section 5 concludes with a number of new directions to consider.

To this end, we define a computation graph $G_{M^{\prime},x}$ on $B+1=O(T(n)/b(n))$ nodes, a directed acyclic graph whose edges model the information flow from earlier time blocks in the computation to later time blocks: the reads and writes of $M^{\prime}$ and the head movements across blocks of tape. Our notion is very similar to the computation graphs defined in [HPV75, PR80]. Eventually, the computation being performed on the $(B+1)$-node graph $G_{M^{\prime},x}$ will be viewed as a Tree Evaluation instance of height $B+1$.

Our graph $G_{M^{\prime},x}$ has a node $i$ for each time block $i\in\{0,1,\ldots,B\}$, and the edges will indicate which previous time block contents need to be read in order to compute the content of the tape blocks accessed during time block $i$. In particular, we say that all tape blocks on the two tapes are active during time block $0$, and for $i>0$, a tape block is active during time block $i$ if the tape head visits some cell of the block during time block $i$. We put an edge from $(i,j)$ in $G_{M^{\prime},x}$ with $i<j$ if and only if:

• •

  either $j=i+1$, or

• •

  when $M^{\prime}$ is run on input $x$, there is some tape block active during time block $i$ that is not active again until time block $j$. That is, for some tape head $h$, it reads the same tape block $C$ in both time blocks $i$ and $j$, but $h$ does not read tape block $C$ during any time blocks $i+1,\ldots,j-1$. (Alternatively, if some tape block is being accessed for the first time in time block $i$, we have an edge $(0,i)$ to reflect the fact that all tape blocks are defined to be active in time block $0$.)

Observe that each node $i$ has indegree at most $5$: one edge from $i-1$, and at most four other edges for (at most) four active tape blocks during time block $i$ (two active tape blocks for each of the two tapes).

The key insight behind the computation graph notion is that the information needed to simulate $M^{\prime}$ during a time block $j$ only requires knowing the information computed in previous time blocks $i$, where $(i,j)$ is an edge in $G_{M^{\prime},x}$. In particular, the state and head positions of $M^{\prime}$ at the start of time block $j$ may be obtained from the state and head positions at the end of time block $j-1$, so we have the edge $(j-1,j)$, and we have an edge $(i,j)$ for each of those blocks of tape accessed during a time block $i$ which are not accessed again until time block $j$.

Due to the obliviousness of $M^{\prime}$ (Theorem 3.2), we have the following claim:

The claim follows because determining whether $(i,j)$ is an edge just requires us to keep track of the locations of the two tape heads, from some time block $i$ to a later time block $j$. By Theorem 3.2, we can calculate the two tape head locations at any point in time using only $\text{poly}(\log t(n))$ time, so we only have to use $\text{poly}(\log t(n))$ space to keep track of whether a tape block accessed during time block $i$ is only accessed later at time block $j$.

Now we define what is being computed at each node of $G_{M^{\prime},x}$. The content of time block $i$, denoted by $\text{content}(i)$, is defined as follows:

• •

  $\text{content}(0)$ is the initial configuration of $M^{\prime}$ running on the input $x$ of length $n$, encoded in $n+O(1)$ bits. (Recalling we have $t(n)\geq n^{2}$, we will eventually set $b(n)\geq n$. Thus the initial configuration of $M^{\prime}$ on $x$ can “fit” in one tape block.)

• •

  For $i\in\{1,\ldots,B\}$, $\text{content}(i)$ encodes information about the status of $M^{\prime}$ on $x$ at the end of time block $i$: the state of $M^{\prime}$, the two tape head positions, and a list of the contents of those tape blocks accessed during time block $i$. As there are at most four such tape blocks which may have been accessed during time block $i$, $\text{content}(i)$ can be encoded in $O(b(n)+\log t(n))\leq O(b(n))$ bits.

Note that for every fixed $j\in[B]$, if we are given $\text{content}(i)$ for all edges $(i,j)$ in $G_{M^{\prime},x}$, then we can compute $\text{content}(j)$ in $O(b(n))$ time and space, by simply simulating $M^{\prime}$ for $b(n)$ steps on the tape blocks of the relevant $\text{content}(i)$ values.

Our goal is to determine $\text{content}(B)$, the content of the final time block, which will contain either an accept or reject state and determine the answer.

To do this, we construct a Tree Evaluation instance in which the root node computes $\text{content}(B)$, its children compute $\text{content}(i)$ for all $i$ such that $(i,B)$ is an edge in $G_{M^{\prime},x}$, and so on; the leaves of our Tree Evaluation instance will compute $\text{content}(0)$, the initial configuration of $M^{\prime}$ on $x$. This transformation is analogous to how depth-$d$ Boolean circuits of fan-in $F$ can be modeled by formulas of depth-$d$ and size at most $O(F^{d})$, by tracing over all possible paths from the output gate of the circuit to an input gate of the circuit; see for example [Juk12, Chapter 6].

More precisely, we define a tree $R_{M^{\prime},x}$ of height at most $B+1$ and fan-in at most 5, with a root node that will evaluate to $\text{content}(B)$. Each node $v$ of $R_{M^{\prime},x}$ is labeled by a distinct path from some node $j$ in $G_{M^{\prime},x}$ to the node $B$ of $G_{M^{\prime},x}$. Inductively, we define the labels as follows:

• •

  the root node of $R_{G^{\prime}}$ is labeled by the empty string $\varepsilon$ (the empty path from $B$ to itself), and

• •

  for every node $v$ in $R_{M^{\prime},x}$ labeled by a distinct path $P$ from $j$ to $B$, and for every node $i$ with an edge to $j$ in $G_{M^{\prime},x}$, the node $v$ has a child $w$ in $R_{M^{\prime},x}$ labeled by the path which takes the edge $(i,j)$ then the path $P$ to $B$.

Observe that paths $P$ of length $\ell$ from a node $j$ to node $B$ can be encoded in $O(\ell)$ bits, since the indegree of each node is at most $5$. Furthermore, given such a path $P$ encoded in this way, observe we can determine the node $j$ at the start of $P$ in $\text{poly}(\log t)$ space, by making repeated calls to the edge relation (as in 3.3).

The desired value to be computed at node $v$ (labeled by a path from $j$ to $B$) is precisely $\text{content}(j)$. For $j=0$, this value is just the initial configuration of $M^{\prime}$ on $x$, which can be produced immediately in $O(n)$ time and space. For $j>0$, $\text{content}(j)$ can be computed in $O(b(n))$ time and space given the values of the children of $v$. Since $G_{M^{\prime},x}$ has at most $B+1$ total nodes, the height of $R_{M^{\prime},x}$ is at most $B+1$. By induction, the value of the root of $R_{M^{\prime},x}$ is precisely $\text{content}(B)$.

While the tree $R_{M^{\prime},x}$ has $2^{\Theta(B)}\leq 2^{\Theta(T(n)/b(n))}$ nodes, observe that for any given node $v$ of $R_{M^{\prime},x}$ (labeled by a path to $B$), we can easily compute the labels of the children of $v$ in $\text{poly}(\log t(n))$ space, using 3.3 to compute the edges of the graph $G_{M^{\prime},x}$. Thus, it takes only $\text{poly}(\log t(n))$ additional space to determine the children of any given node of $R_{M^{\prime},x}$, and this space can be immediately reused once these children are determined. So without loss of generality, we may assume we have random access to the tree $R_{M^{\prime},x}$, its leaves, and its functions at each node.

Finally, we call the Cook-Mertz Tree Evaluation algorithm (Theorem 2.2) in its most general form on $R_{M^{\prime},x}$. Recall that the space bound of this algorithm, for trees of height at most $h$, fan-in at most $d$, computing $b$-bit values at each node, is

$$O(d\cdot b+h\log(d\cdot b)).$$

For us, $d=5$, $b=b(n)$, and $h=O(T(n)/b(n))\leq O(t(n)\log t(n))/b(n)$. We only use $O(b(n))$ additional time and space for each function call to compute some $\text{content}(j)$, and we can reuse this space for every separate call. Therefore our space bound is optimized up to constant factors, by setting $b(n)$ such that

$$b(n)^{2}=\Theta(t(n)\log t(n)\cdot\log b(n)),$$

so $b(n)=\sqrt{t(n)}\cdot\log t(n)$ suffices. This completes the proof of Theorem 3.1.

We start by refining the computation graph notion from Theorem 3.1. Here, our computation graph $G_{M^{\prime},x}$ is similar but not identical to that of [HPV75] and the warm-up Theorem 3.1. Because we will allow for space bounds which are smaller than the input length $n=|x|$, we have to make several modifications to $G_{M^{\prime},x}$ to fit the specifications of Tree Evaluation. We define the set of nodes in $G_{M^{\prime},x}$ to be

$$S=\{(h,i),(h,0,i)\mid h\in[p],i\in[B]\}.$$

Intuitively, each $(h,i)\in[p]\times[B]$ will correspond to the content of the relevant block of tape $h$ after time block $i$, while each $(h,0,i)$ will be a source node in $G_{M^{\prime},x}$ corresponding to the content of the $i$-th block of tape $h$ when it is accessed for the first time, i.e., the initial configuration of the $i$-th block of tape $h$.⁷⁷7A little explanation may be in order. In the warm-up Theorem 3.1, we assumed $t(n)\geq n^{2}$, so that the entire initial configuration of the machine on $x$ could fit in a length-$b(n)$ block. This made the leaf nodes of our Tree Evaluation instance $R_{G^{\prime}}$ particularly easy to describe. For $t(n)\ll n^{2}$, we may have $|x|=n\ll b(n)$, so the input $x$ may not fit in one tape block. To accommodate this possibility and obtain a clean reduction to Tree Evaluation in the end, we define multiple source nodes in $G_{M^{\prime},x}$ to account for different $b(n)$-length blocks of input $x$ in the initial configuration of $M^{\prime}$ on $x$, along with $b(n)$-length blocks of all-blank tape when these blocks are accessed for the first time. (We imagine that on each tape, the tape blocks are indexed $1,2,\ldots$ starting from the leftmost block, with up to $B$ tape blocks for each tape.) We think of all $(h,0,i)$ nodes as associated with “time block $0$”.

Each node $(h,i)\in[p]\times[B]$ is labeled with an integer $m_{(h,i)}\in\{-1,0,1\}$, indicating the tape head $h$ movement at the end of time block $i$:

$$m_{(h,i)}=\begin{cases}~{}1&\text{ if the head $h$ moves one tape block to the right of the current tape block},\\ -1&\text{ if $h$ moves one tape block to the left, and}\\ ~{}0&\text{ if $h$ stays in the same tape block for both time blocks $i$ and $i+1$.}\end{cases}$$

Next, we describe the edges of $G_{M^{\prime},x}$; there are two types. For each $h,h^{\prime}\in[p]$ and $i,j\in[B]$ with $i<j$, the edge $((h^{\prime},i),(h,j))$ is put in $G_{M^{\prime},x}$ if either:

• •

  $j=i+1$, or

• •

  while $M^{\prime}$ is running during time block $j$, the tape block accessed by $h^{\prime}$ during time block $i$ is not accessed again until time block $j$. That is, tape head $h^{\prime}$ reads the same tape block $T$ in both time blocks $i$ and $j$, but head $h^{\prime}$ does not read tape block $T$ during any of the time blocks $i+1,\ldots,j-1$.

For $h,h^{\prime}\in[p]$ and $i,j\in[B]$, the edge $((h^{\prime},0,i),(h,j))$ is put in $G_{M^{\prime},x}$ if, while $M^{\prime}$ is running during time block $j$, the tape head $h^{\prime}$ accesses its $i$-th tape block for the first time in the computation. (For example, note that , for all $h,h^{\prime}$, $((h^{\prime},0,1),(h,1))$ is an edge.)

Observe that the indegree of each node $(h,j)\in[p]\times[B]$ is at most $2p$ for all $j>0$: for all $h^{\prime}\in[p]$, there is an edge from $(h^{\prime},j-1)$ to $(h,j)$ for $j>1$ (and from $(h^{\prime},0,1)$ to $(h,1)$ for $j=1$), and there is an edge from a node labeled by $h^{\prime}$ (either of the form $(h^{\prime},i_{h^{\prime},j})$ or $(h^{\prime},0,i_{h^{\prime},j})$) to $(h,j)$, indicating which block of tape $h^{\prime}$ is needed to compute the block of tape $h$ during time block $j$. (Note that some of these edges might be double-counted, so the indegree is at most $2p$.)

The obvious way to store the computation graph $G_{M^{\prime},x}$ uses $O(B\log B)$ bits. To save space, we will be more careful, and use additional observations on the structure of such computation graphs. (These observations are similar but not identical to those used in the separation of ${\sf NTIME}[n]$ and ${\sf TIME}[n]$, of Paul-Pippenger-Szemerédi-Trotter [PPST83].)

Recall that each node $(h,i)$ is labeled by a head movement $m_{(h,i)}\in\{-1,1,0\}$ indicating whether the tape block of head $h$ is decremented by $1$, incremented by $1$, or stays the same, at the end of time block $i$. Our key observation is that the numbers $m_{(h,i)}$ alone already tell us the entire structure of the graph $G_{M^{\prime},x}$. This immediately implies that every possible guess of $G_{M^{\prime},x}$ can be encoded in only $O(B)$ bits: we only need a constant number of bits for each of the $O(B)$ nodes.

In particular, for an index $i\in[B]$, we define $\text{block}(h,i)\in[B]$ to be the index of the tape block of tape $h$ being accessed at the start of time block $i$. For all $h\in[p]$, we have $\text{block}(h,1)=1$, and for $i>1$, by definition of the $m_{(h,i)}$ we have

$\displaystyle\text{block}(h,i)=1+\sum_{j=1}^{i-1}m_{(h,j)}.$

(1)

Equation (1) is true because each $m_{(h,j)}$ tells us how the index of the tape block of tape $h$ changes at the end of time block $j$, which is the same as the tape block index at the start of time block $j+1$.

For $i<j$, observe that there is an edge from $(h^{\prime},i)$ to $(h,j)$ in $G_{M^{\prime},x}$ if and only if either:

• •

  $j=i+1$, or

• •

  $\text{block}(h^{\prime},i)=\text{block}(h^{\prime},j)$ and for all $k\in\{i+1,\ldots,j-1\}$, $\text{block}(h^{\prime},k)\neq\text{block}(h^{\prime},i)$. (The tape block accessed by $h^{\prime}$ in time block $i$ is not accessed again until time block $j$.)

Furthermore, there is an edge from $(h^{\prime},0,i)$ to $(h,j)$ in $G_{M^{\prime},x}$ if and only if $i=\text{block}(h^{\prime},j)$ and for all $k\in\{1,\ldots,j-1\}$, $\text{block}(h^{\prime},j)\neq\text{block}(h^{\prime},k)$. (The tape block accessed by $h^{\prime}$ in time block $j$ was never accessed before, and its index is equal to $i$.)

We will use a few claims about the block function and the computation graph.

To summarize, we can encode $G_{M^{\prime},x}$ in $O(B)$ bits, and given such an encoding, we can determine any desired edge $(u,v)$ of the graph in logspace.

Similarly to our warm-up Theorem 3.1, we define contents for each of the nodes of $G_{M^{\prime},x}$. For all $h\in[p]$ and $i\in[B]$, we define $\text{content}(h,0,i)$ for the source nodes $(h,0,i)$ as follows:

• •

  If $h>1$, then we are reading a tape $h$ that does not contain the input. In this case, $\text{content}(h,0,i)$ is defined to be all-blank tape content: $b(n)$ blanks, with the tape head at the leftmost cell of the block, and head position equal to $(i-1)\cdot b(n)$. (Note that, assuming we start numbering tape cells at $0$, $(i-1)\cdot b(n)$ is the leftmost cell of the $i$-th block of tape.)

• •

  If $h=1$, then we may need to read portions of the input $x$ of length $n$. If $i>\lceil n/b(n)\rceil$, then the $i$-th tape block of tape $1$ does not contain any symbol of $x$, and $\text{content}(1,0,i)$ is defined to be all-blank tape content as above. Otherwise, if $i\leq\lceil n/b(n)\rceil$, then $\text{content}(1,0,i)$ is defined to be the relevant $b(n)$-length substring of $x$ (possibly padded with blanks at the end) with the tape head at the leftmost cell of the block, head position equal to $(i-1)\cdot b(n)$, and the initial state of $M^{\prime}$ included if $i=0$.

Note that the source nodes of our $G_{M^{\prime},x}$ will eventually be the leaf nodes of the Tree Evaluation instance; in the above, we are also defining the values of those leaves.

For $h\in[p]$ and $i\in[B]$, we define $\text{content}(h,i)$ of node $(h,i)$ similarly as in Theorem 3.1: it is a string encoding the pair $(h,i)$, the state of $M^{\prime}$ and the head position of tape $h$ at the end of time block $i$, and the content of the tape block read by head $h$ at the end of time block $i$. With a reasonable encoding, $\text{content}(h,i)$ can be represented in $O(b(n)+\log t(n))\leq O(b(n))$ bits, and our computation graph $G_{M^{\prime},x}$ has been set up (just as in Theorem 3.1) so that given the strings $\text{content}(u)$ for all nodes $u$ with edges to $(h,j)$, the string $\text{content}(h,j)$ can be computed in $O(b(n))$ time and space.

In what follows, we enumerate over all possible $O(t(n)/b(n))$-bit choices $G^{\prime}$ of the encoding of the computation graph $G_{M^{\prime},x}$ on $O(B)\leq O(t(n)/b(n))$ nodes. For each $G^{\prime}$, we construct a Tree Evaluation instance $R_{G^{\prime}}$ based on $G^{\prime}$, which will attempt to simulate $M^{\prime}$ on $x$ assuming $G^{\prime}=G_{M^{\prime},x}$. We will set up $R_{G^{\prime}}$ so that the following conditions hold:

• •

  If $G^{\prime}\neq G_{M^{\prime},x}$, this means that at the end of some time block $i$, some tape head $h$ of $M^{\prime}$ on $x$ moves inconsistently with the guessed label $m_{(h,i)}$ in $G^{\prime}$. In this case, evaluating $R_{G^{\prime}}$ will result in a special FAIL value at the root.

• •

  If $G^{\prime}=G_{M^{\prime},x}$, then $R_{G^{\prime}}$ will evaluate to $\text{content}(1,B)$ at the root, which will include either an accept or reject state at the end of the computation of $M^{\prime}$ on $x$. Thus we will be able to conclude decisively whether $M$ accepts or rejects $x$ after this call to Tree Evaluation.

Finally, if we exhaust all computation graphs $G^{\prime}$ and always receive FAIL from all Tree Evaluation calls, we then increase our guess of $t(n)$ by $1$ (starting from $t(n)=n$), and restart the entire process. (Recall that we do not assume $t(n)$ is constructible.) Eventually, we will choose an appropriate $t(n)$, in which case the above enumeration of graphs $G^{\prime}$ will result in either acceptance or rejection.

We now define the functions at the nodes of our Tree Evaluation instance $R_{G^{\prime}}$. These functions will allow us to detect when the current graph $G^{\prime}$ we are considering has an error. We have to be a little careful here, as the Cook-Mertz algorithm is only guaranteed to produce the value of the root of a given tree, and not the values of any intermediate nodes along the way. (Indeed, the values of other nodes may become quite “scrambled” from evaluating a low-degree extension of the functions involved.)

For each tape $h\in[p]$ and time block $i\in[B]$, we define a time block function $F_{h,i}$ which attempts to simulate $M^{\prime}$ over time block $i$, and to output $\text{content}(h,i)$, the content of the relevant block of tape $h$ at the end of time block $i$.

First, we choose an encoding of $\text{content}(h,i)$ strings so that there is also a special FAIL string of length $O(b(n))$, which is distinct from all valid content strings.

• •

  The input to $F_{h,i}$ consists of up to $2p$ strings of length $O(b(n))$. Some strings may be $O(b(n))$-bit FAIL strings. In the case where $G^{\prime}=G_{M^{\prime},x}$, $p$ of the input strings have the form $\text{content}(h^{\prime},i-1)$ (or $\text{content}(h^{\prime},0,1)$ if $i=1$) for all $h^{\prime}\in[p]$. These content strings contain the index of the node in $G^{\prime}$ they correspond to, the state $q$ of $M^{\prime}$ at the start of time block $i$, the content of the relevant tape blocks at the end of time block $i-1$, and the head positions of all $p$ tapes at the start of time block $i$, where each head position is encoded in $O(\log b(n))$ bits. When some of the tape blocks accessed in time block $i$ were not accessed in the previous time block, there are also (up to) $p$ other strings $\text{content}(u_{1}),\ldots,\text{content}(u_{p})$ which contain tape block content $c_{1},\ldots,c_{p}$ for each of the $p$ tapes at the start of time block $i$.

• •

  The output of $F_{h,i}$ is defined as follows. First of all, if some input string is a FAIL string, then $F_{h,i}$ immediately outputs FAIL as well. In this way, a single FAIL detection at any node will propagate to the root value of $R_{G^{\prime}}$.

  Assuming no FAIL strings have been given as input, $F_{h,i}$ attempts to simulate $M^{\prime}$ for time block $i$, using the given content strings. While simulating, $F_{h,i}$ checks that for all $h^{\prime}\in[p]$, the tape head $h^{\prime}$ moves consistently with the integer $m_{(h^{\prime},i)}\in\{0,1,-1\}$. In particular, if $m_{(h^{\prime},i)}=-1$ then it checks tape head $h^{\prime}$ moves to its left-adjacent tape block at the end of time block $i$, if $m_{(h^{\prime},i)}=1$ then it checks $h^{\prime}$ moves to its right-adjacent tape block, and if $m_{(h^{\prime},i)}=0$ then it checks $h^{\prime}$ remains in the same tape block. If all heads $h^{\prime}$ move consistently with the integers $m_{(h^{\prime},i)}$, then the output of $F_{h,i}$ is set to be $\text{content}(h,i)$. Otherwise, the output of $F_{h,i}$ is FAIL.

Observe that $F_{h,i}$ can be computed in $O(b(n))$ time and space, by simply simulating $M^{\prime}$ for $b(n)$ steps, starting from the contents $c_{1},\ldots,c_{p}$ for each of the tapes, and the state and head information given. Furthermore, by setting $b^{\prime}(n)=\Theta(b(n))$ appropriately, we may think of each $F_{h,i}$ as a function from an ordered collection of $2p$ separate $b^{\prime}(n)$-bit strings, to a single $b^{\prime}(n)$-bit string. These will be the functions at the nodes of our Tree Evaluation instance.