# Savitch's theorem and time relation

We know that $NTIME(t(n)) \subseteq DSPACE(t(n))$ and we know - by Savitch's theorem - that $NSPACE(s(n)) \subseteq DSPACE(s^2(n))$.

By the space/time relation $(s(n) \leq t(n))$ I know that $NTIME(t(n)) \subseteq NSPACE(t(n))$, then by Savitch's theorem $NSPACE(t(n)) \subseteq DSPACE(t^2(n))$ and not $DSPACE(t(n))$, as stated above.

Where am I wrong?

In any case, $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \;$ and $\; \{0\} \subseteq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ , $\;$ even though $\: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\} \neq \{\hspace{-0.02 in}0,\hspace{-0.05 in}1,\hspace{-0.04 in}2\hspace{-0.02 in}\}$ .
• But I'm not adding anything to Savitch's theorem, I'm starting from $NSPACE(t(n))$ and getting $DSPACE(t^2(n))$. Then why Savitch did it this way, if we already know $NSPACE(t(n)) = DSPACE(t(n))$ due to the fact we can reuse space? Feb 4 '17 at 8:41
• How do "we already know" ​ NSPACE(t(n)) $\subseteq$ DSPACE(t(n)) ​ "due to the fact we can reuse space?" ​ ​ ​ ​
• Because $NTIME(t(n)) \subseteq NSPACE(t(n)) \subseteq DSPACE(t(n))$, the first assertion is due to the fact $t(n) \leq s(n)$ and $NTIME(t(n)) \subseteq DSPACE(t(n))$ is due to the fact that when you simulate a NTM you need at most O(t(n)) space. Feb 4 '17 at 8:50