1
$\begingroup$

I think this is again an easy one:

$DTIME(f(n)) \subset DSPACE(f(n))$

They say its trivial but I dont see it, why?

And would

$DTIME(f(n^2)) \subset DSPACE(f(n^2))$

also be true? if yes why or why not?

$\endgroup$
1
$\begingroup$

In each time step, the Turing machine can only move one position. Therefore, after $T$ time steps, the Turing machine can only have visited at most $T$ different positions, so its space usage (the number of cells it has visited or written to) must be at most $T$. Thus, the space complexity of any Turing machine is at most its time complexity.

$\endgroup$
  • $\begingroup$ ok thats a nice explanation, thank you! you stated the space usage as the number of cells the tm has written to, so if it doesnt write to cell, just goes to the next then this doesnt counts as used space? $\endgroup$ – simplesystems Jun 26 '18 at 17:21
  • $\begingroup$ @simplesystems, I've edited. We can count the number of cells visited in the space complexity, and all of the reasoning remains valid. Thanks for helping me improve this answer! $\endgroup$ – D.W. Jun 26 '18 at 17:27
1
$\begingroup$

If space is greater than time, as it must surf the space (in the related Turing machine), it will be contradicted by time is less than space. Hence, we can find that all problems which are in $DTIME(f(n))$ are in $DSPACE(f(n))$. and the proof is completed.

On the other hand, the size of input is important. Hence, if we set $m = n^2$ we reach to the first relation. Hence, it is true again.

$\endgroup$
  • $\begingroup$ what do you mean by "surf the space" and what is when time is greater than space? $\endgroup$ – simplesystems Jun 26 '18 at 15:24
  • $\begingroup$ @simplesystems I mean moving head of the Turing machine. $\endgroup$ – OmG Jun 26 '18 at 15:26
  • $\begingroup$ and what is when time greater is than space? $\endgroup$ – simplesystems Jun 26 '18 at 15:32
  • $\begingroup$ @simplesystems what is what? $\endgroup$ – OmG Jun 26 '18 at 15:36
  • $\begingroup$ you assume that if space is greater than time... I ask what is if time is greater than space, sorry edited $\endgroup$ – simplesystems Jun 26 '18 at 15:38

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.