# What role does the lower bound play in the statement of Savitch's Theorem?

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

I don't understand why the requirement that $$f\in \Omega (\log(n))$$ is necessary for the proof to work. I.e., where exactly does the proof of the theorem break down if $$f(n) \leq \log(\log(n))$$?

I understand the main ideas of the proof, including the use of the $$\text{CANYIELD}$$ recursive subroutine and the trick that allows you to handle the case where $$f$$ is not space-constructible. I just don't understand the role of the lower bound on $$f$$ in the statement of the theorem.

The proof relies on the following property: the time-complexity of a decider machine is at most exponential in its space-complexity. The bound assumptions, namely $$f(n)\geq \log n$$, are sufficient for that property to hold. Specifically, if you consider a 2-tape TM machine that decides its language in sub-linear space $$f(n)$$ (in sub-linear space, we need a separate read-only tape where the input is written, and a working tape, and the space complexity is measured only w.r.t to the working tape), then the number of configurations the machine can be in is $$n\cdot 2^{O(f(n))}$$ (the additional factor of $$n$$ is because we need to consider the different possible head positions of the input tape).
Now it is not hard to see that $$n\cdot 2^{O(f(n))}$$ is exponential in $$f(n)$$ when the condition $$f(n)\geq \log n$$ holds. If you assume however that $$f$$ is considebraly small, for example, $$f(n)\leq \log(\log(n))$$, then you get that the runtime of the machine is bounded by $$n\cdot 2^{O(f(n))} = 2^{\log n + O(f(n))}$$. On the other hand, $$\lim\limits_{n\to \infty} \frac{2^{O(f(n))}}{2^{\log n + O(f(n))}} = 0$$, and thus the property that the runtime of the machine is at most exponential in its space-complexity does not hold anymore.
Edit 1: as a simple example, note that a machine with space-complexity $$f(n) \leq \log(\log (n))$$ can have linear runtime as reading the input does not count as used space.
Edit 2 (an intuition for those who are familiar with the proof of Savitch's theorem): if you're familiar with the proof of Savitch's theorem, then an intuition to why the property mentioned in the solution is sufficient is because the depth of the recursion tree in the deterministic simulation is logarithmic in the runtime of the machine which equals $$2^{O(f(n))}$$ when the property holds. So the recursion stack ends up using space proportional to $$O(f^2(n))$$ as per node in the tree, we need to store at least a configuration that uses $$f(n)$$ space. However, when, for example, we consider sub-linear space-complexity $$f(n)\leq log(log(n))$$, then the runtime is $$n\cdot 2^{O(f(n))}$$, and we need to store per node an additional $$\log(n)$$ bits for the input-tape head's position, and the recursion depth increases to $$\log n + O(f(n))$$ as well. Thus, in this case, the recursive deterministic simulation uses more than quadratic space, and it is not clear how to avoid that when/if possible without using more assumptions.
• Perhaps another reason is that in the "recursive" deterministic simulation we need to store $f(n)$ copies of the tape contents. As you remark each configuration needs $f(n)$ space for the working tape, but also $\log n$ for the position on the input tape. We do not want $\log n$ to be larger than $f(n)$. Commented Aug 15 at 14:10
• I finally think I get it, the second edit helped a lot. To summarize, machines that run in sublinear space require a read-only input tape whose presence increases the total configurations (and thus also maximum run time) to $n2^{O(f(n))}$. Storing each configuration takes $\log(n2^{O(f(n))}) = \log(n) + O(f(n))$ space, times the new recursion depth of $\log(n) + O(f(n))$ gives a total space usage of $\log^2(n) + O(f(n))\log(n) + O(f^2(n))$. When $f(n) \geq \log(n)$ this yields the original theorem. Otherwise when $f(n) < \log(n)$ the space usage is $O(\log^2(n))$. Is this correct? Commented Aug 15 at 15:49