The crux of Savitch's Theorem

In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):


We need to simulate an $f(n)$ space NTM deterministically. A naive
approach is to proceed by trying all the branches of the NTM’s
computation, one by one. The simulation needs to keep track of which
branch it is currently trying so that it is able to go on to the next
one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$
steps and each step may be a nondeterministic choice. Exploring the
branches sequentially would require recording all the choices used on
a particular branch in order to be able to find the next branch.
Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our
goal of $O(f^2(n))$ space. (Sipser, "Introduction to the Theory of Computation" 334)

He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c_2$ is reachable from some other configuration $c_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c_1, c_n, t)$ results in two recursive calls $CANYIELD(c_1, c_m, t/2)$ and $CANYIELD(c_m, c_n, t/2)$, and so on until the "distance" between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.

So, there are two questions I have.

• I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c_m$ is negligible?

• I don't understand why we need $2^{O(f(n))}

A program running in space $f(n)$ can take up to $2^{O(f(n))}$ time (the constant depends on the alphabet size). Hence, it could potentially make up to $2^{O(f(n))}$ non-deterministic choices. Naively, going over all of them requires that many steps. Savitch's theorem shows how this can be accomplished using only $O(f(n)^2)$ space. The idea is to use a recursive "meet in the middle" approach. Let an upper bound on the running time of the machine be $T$. The initial tape is the the state of the tape when the machine is started up. The final tape is the state of the tape at the end of the execution. We "guess" (i.e., go over all possibilities) the final tape, and try to verify that this final tape can be reached from the initial tape. At the first level of the recursion, we "guess" the contents $X$ of the tape at time $T/2$. We then recurse into two similar tasks:

• Verify that $X$ can be reached in $T/2$ steps from the initial tape.

• Verify that the final tape can be reached from $X$ in $T/2$ steps.

Each of these is solved by recursion. We can reuse the space of the first task when we execute the second task. The base of the recursion is when the number of steps is one, in which case we can verify the claim directly. If it checks out, great. Otherwise, we signal failure, and this signal prompts us to make the next guess (at the appropriate level of recursion).

Each level of the recursion requires storage space of size $f(n)$, and there are $\log T = O(f(n))$ levels, so the total space consumption is $O(f(n)^2)$.

StackExchange Computer Science Q#22745, answer score: 6