# proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$

for $$S(n) \geq \log{(n)}$$, with $$S(n)$$ being fully time-constructible...

As an attempt, isn't the proof for this problem almost exactly the same as the proof for

$$DSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$

The proof for $$DSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ says that given $$S(n)$$ space, one can come up with a finite number of $$TM$$ configurations that can be expressed as $$c^{S(n)}$$, for some constant $$c$$. Since $$c^{S(n)} \in o(n)$$, we can use a 'clock' to count up to $$c^{S(n)}$$ to make the $$TM$$ a decider ....

But I seem to see that the same logic also holds for $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ ... since whether it is deterministic space or non-deterministic space, the number of configurations within space $$S(n)$$ remains finite and can be counted up to $$c^{S(n)}$$ .... am I correct or am I missing something ?

• How do you simulate a nondeterministic machine, using a deterministic machine? – Yuval Filmus Jun 8 at 7:27
• @YuvalFilmus, ... i guess you could make a tree of all configurations that can be reached by a nondeterministic machine, then do a breadth-first search ... – Link L Jun 8 at 10:43
• Would you then say that the proof is almost exactly the same? – Yuval Filmus Jun 8 at 10:44
• @YuvalFilmus oh right ! --- there's a difference, the first proof (for $DSPACE$) just simulates the deterministic TM and uses the counter, while the second (for $NSPACE$) has to construct the tree (along with the counter).. – Link L Jun 8 at 10:47