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...
2026-04-01 20:30:55.1775075455
Why is it obvious that P is contained in PSPACE and NP contained in NPSPACE?
1k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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).