Return to 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 (or the weaker requirement that $f(n) \geq n$ that Sipser uses in Introduction to the Theory of Computation). 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.

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.

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 (or the weaker requirement that $f(n) \geq n$ that Sisper uses in Introduction to the Theory of Computation). 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.

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 (or the weaker requirement that $f(n) \geq n$ that Sipser uses in Introduction to the Theory of Computation). 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.

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 (or the weaker requirement that $f(n) \geq n$ that Sisper uses in Introduction to the Theory of Computation). 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.

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 (or the weaker requirement that $f(n) \geq n$ that Sisper uses in Introduction to the Theory of Computation). 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.