A small issue regarding the proof of Savitch's Theorem

Question

Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.

The proof I am familiar with states the following: we are given a non-deterministic turing machine $N$ for our language $A$. It is known that for inputs in $A$ that $N$ accepts by using $O\left( f \left( n \right)\right)$ space. I would like to construct a deterministic turing machine $M$ that accepts inputs from $A$ in $O\left( \left( f \left( n \right)\right) ^2 \right)$ space, and this will prove the correctness of the theorem.

Knowing that $s,t-Path$ is in $DSPACE\left( \left(\log{n} \right)^2\right)$, we define the (deterministic) turing machine $M$ to work the following way (on a given input $a$:

1. Construct the configuration graph for the computation of $N$ on $a$.
2. Run a space-efficient algorithm for $s,t-Path$, where $s$ is the initial configuration and $t$ is the accepting configuration (assume, w.l.o.g., only one accepting configuration exists. If not, adjust $N$ accordingly so it will hold).
3. If such a path was found, accept. Else, reject.

Phase (2) takes $O\left( \left(\log{n} \right)^2\right)$ space. But what about phase (1)? How Am I to construct the configuration graph, which has $\Theta \left( 2^{O\left( f \left( n \right) \right)} \right)$ vertices, in only $O\left( \left(\log{n} \right)^2\right)$ space?

I read that the graph can be built on the fly, but then - how do we check whether an edge exists? If the graph itself is not fully computed ahead of time, we must always call to $N$ to check what are the destination configurations from our current configuration. Now, this gets a bit tricky, as $N$ is not part of the input. Should we assume we can somehow approach it? Without taking time? Where is $N$ maintained? This takes space as well.

I am aware my question is not the main focus of the theorem, but its something that bugs me in this proof. Or are there better proofs? (Also, how can this small issue be better explained, in this proof?)

Answer 1

Lemma: let $N$ be a deterministic Turing machine running in space $f(n)$. Then it is possible to know if there is a transition between two configurations (that both use space $\leqslant f(n)$) in space $\mathcal{O}(f(n))$.

Proof: Using alphabet $\{0,1\}$, a configuration can be encoded using the tape content, the position of the head and the state of the Turing machine. That means that there exists $\alpha > 0$ such that there are at most $m \leqslant 2^{\alpha f(n)}$ configurations that use space $\leqslant f(n)$. Know given $i, j\leqslant m-1$, if you want to know if there is a transition between $i$ and $j$, you have to:

• write $i$ and $j$ (at most $\alpha f(n)$ bits);
• move the head to the right position (using a counter $\leq f(n)$);
• simulate all transitions from configuration $i$.

All this can indeed be done in space $\mathcal{O}(f(n))$.