It seems that if an algorithm ran in polynomial time on a deterministic Turing machine it would not require more than polynomial space because it would basically take more than polynomial time to use up that much space. But really, I am not sure...
Asked
Active
Viewed 1,021 times
1 Answers
5
Hint: (assuming for simplicity a deterministic or non-deterministic Turing machine with a single tape) in $n$ steps of a computation, a Turing machine can't visit more than $n+1$ positions on its tape. So the number of steps (time) gives you a linear bound on the number of tape positions (space).
To put that more concisely: a Turing machine (either deterministic or non-deterministic) can't consume space (tape positions) faster than it consumes time (computational steps).
Rob Arthan
- 48,577
-
Thank you for the clarification. This is a very clear and concise answer! – Ralff Mar 13 '17 at 02:18