0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.