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

Question

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.

Answer 1

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.