Savitch theorem and its assumption

Question

famous Savitch theorem states:

For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$

Why we need an assumption that $f\in\Omega(\log(n))$?

Thank you.

Answer 1

This seems like a technicality, but basically is necessary for the proof to go through. Recall that the first part does not care about the language: it just states that $\sf Connectivity$ (on a $n$-vertex graph) is in $\sf DSPACE(\log^2 n)$.

The second part, however, uses the fact that a state of the non-deterministic machine for a language in $L\in\sf NSPACE(f(n))$ can be encoded by $O(f(n))$ bits -- so that you are left with a graph on $2^{O(f(n))}$ vertices, and apply the connectivity algorithm on it.

But this second claim only holds if $f(n) = \Omega(\log n)$, as otherwise the encoding of a state is not $O(f(n))$ -- it is actually $O(\max(f(n), \log n))$, to really encode the state of the Turing machine. See e.g. p.3 of these lecture notes.