[Solved]: Why is one often requiring space constructibility in Savitch's theorem?

Problem Detail: 

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I understand the requirement for $S(n)$ being in $\Omega(\log n)$, which is clear from the proof. But no proof I have seen so far explicitly uses that $S(n)$ is space constructable.

My explanation: in order to call the procedure REACH (or PATH or whatever you like to call it), the last parameter needs to be "spelled out", and in order not to leave our space bounds of S(n) for one call, we must not need more than $S(n)$ space to write it down.

Asked By : Cornelius Brand

Answered By : Ran G.

I believe your explanation is correct. The st-REACH subroutine gets $(s,t,\ell)$ as an input, and finds whether or not $t$ is reachable from $s$ by $\ell$ steps. $s$ and $t$ will be the initial and final configurations, and $\ell=2^{O(s(n))}$, the upper bound on the number of different configurations.

In order to set $\ell$ one needs to be able to compute $s(n)$ (or rather, $2^{O(s(n))}$). If this process takes more than $O(s^2(n))$ space, then the entire machine will have space more than the allowed. It is possible that even $O(s^2(n))$ is too much because of the recursive call to st-REACH (is there any other possible reason?), but I didn't check that.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11168

 Ask a Question

 Download Related Notes/Documents