# Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem

I was wondering whether someone could help me resolve an issue I have understanding the proof given for Savitch’s theorem in the Sipser text (3rd edition). The question I have is more or less identical to the first question given in a previous post (The crux of Savitch's Theorem); which has remained unanswered – hence I’ll re-state the question and elaborate on the details more in this post.

On page 335, the function ‘CANYIELD’ is described:

CANYIELD = “On input c1, c2, and t:

1. If t = 1, then test directly whether c1 = c2 or whether c1 yields c2 in one step according to the rules of N. Accept if either test succeeds; reject if both fail.
2. If t > 1, then for each configuration cm of N using space f(n):
3.       Run CANYIELD(c1, cm, t/2 ).

4.       Run CANYIELD(cm, c2, t/2 ).

5.       If steps 3 and 4 both accept, then accept.

6. If haven’t yet accepted, reject.”

My question concerns step 2 of this procedure: namely how exactly does it select cm of N? It says ‘for each configuration of N’ – but as far as I can tell no specific method is described for how M can implement this [which is important, since we need to be able to verify that this selection can be done in O(f2(n))]. It is not obvious to me how you would be able to know what all of N’s legal configurations are for a given input without running it and storing the computation tree in memory – which obviously we cannot do because it could be exponential in the size of the input. Any help on this would be greatly appreciated.

You can enumerate every possible configuration $$c_m$$ of $$N$$, this process takes only $$O(f(n))$$ space

First, lets consider the number of configuration of $$N$$ that runs in $$f(n)$$ space

If $$N$$ runs in $$f(n)$$ space, has $$c$$ states, $$c = \vert Q \vert$$, and $$g$$ tape symbols, $$g = \vert \Gamma \vert$$, then the total number of strings that can appear on tape are $$g^{f(n)}$$, we can be in any of the $$c$$ states, and the head can be in any of the $$f(n)$$ positions, hence the total number of configurations is $$c \cdot f(n) \cdot g^{f(n)} = O(f(n)2^{f(n)})$$

We can encode these configurations, hence the space needed would be $$O(log(f(n) \cdot 2^{f(n)})) = O(log(f(n)) + log(2^{f(n)})) = O(f(n))$$

Hence we only need $$O(f(n))$$ space

For completion, lets dive into more details of how we can do this in an easy way

A configuration $$c_m$$ as we have shown occupies $$O(f(n))$$ space, meaning it takes $$O(f(n))$$ cells

Each cell is filled with a symbol $$s \in C = Q \cup \Gamma$$, where $$Q$$ is the set of $$N$$ states and $$\Gamma$$ is the tape alphabet

Note that $$\vert C \vert$$ is a constant, and hence each symbol $$s \in C$$ can have a binary encoding of length $$d = \log(\vert C \vert)$$, again $$d$$ is a constant

So, we can replace each symbol $$s \in C$$ by its $$d$$-long binary encoding, and we get a binary configuration of length $$O(d \cdot f(n)) = O(f(n))$$, storing the entire map from symbols to binary code should take only constant space

Now its easy to enumerate every configuration from $$000 \ldots 000$$ to $$111 \ldots 111$$, we can use the stored map to change the configuration from binary string to symbols $$s \in C$$ or vice versa in $$f(n)$$ space