Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?

Question

These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that every problem solvable in polynomial time is also solvable in polynomial space?

Answer 1

The space complexity is always bounded by the time complexity, since you cannot access more than $t(n)$ cells if you run for $t(n)$ time.

So the answer is that there aren't such problems.

• Colonizor48: Thanks for the answer! Would this change if we have a computational model allowing instant access to any given address?(That still takes time to do calculations)
• nir shahar: What would be the definition of space complexity in this case? the usual definition of space complexity using turing machines is "the furthest cell accessed by the turing machine", which makes sense since it has to go one cell at a time (so it will "know" of all cells before it).
• nir shahar: In any case I don't think the intuitive notion of "space" can be larger than the "time", since you will always need at least one operation per "cell of storage" - so the same argument (intuitively) should hold.
• Colonizor48: Allright. Thanks.
• Colonizor48: Although this might not hold with an instruction to access multiple storage cells at once instantly.

Answer 2

No. The amount of space used is upper-bounded by the running time. Each step of the Turing machine can only move one place on the tape. Therefore, $P \subseteq PSPACE$.