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 ?

  • 1
    $\begingroup$ How do you simulate a nondeterministic machine, using a deterministic machine? $\endgroup$ Commented Jun 8, 2020 at 7:27
  • $\begingroup$ @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 ... $\endgroup$
    – Link L
    Commented Jun 8, 2020 at 10:43
  • 1
    $\begingroup$ Would you then say that the proof is almost exactly the same? $\endgroup$ Commented Jun 8, 2020 at 10:44
  • $\begingroup$ @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).. $\endgroup$
    – Link L
    Commented Jun 8, 2020 at 10:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.