0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

I believe you left out big-Os around those bounds.
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}\}$ .

$\endgroup$
8
  • $\begingroup$ So Savitch's theorem gives just a bigger upper bound? $\endgroup$
    – MoreOver
    Feb 4 '17 at 8:34
  • $\begingroup$ Well, the combination you used just gives a bigger upper bound. ​ ​ $\endgroup$
    – user12859
    Feb 4 '17 at 8:36
  • $\begingroup$ 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? $\endgroup$
    – MoreOver
    Feb 4 '17 at 8:41
  • $\begingroup$ How do "we already know" ​ NSPACE(t(n)) $\subseteq$ DSPACE(t(n)) ​ "due to the fact we can reuse space?" ​ ​ ​ ​ $\endgroup$
    – user12859
    Feb 4 '17 at 8:45
  • $\begingroup$ 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. $\endgroup$
    – MoreOver
    Feb 4 '17 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.