0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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) $\endgroup$ Jan 14 at 21:12
  • $\begingroup$ 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). $\endgroup$
    – nir shahar
    Jan 14 at 21:19
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Jan 14 at 21:20
  • $\begingroup$ Allright. Thanks. $\endgroup$ Jan 14 at 21:41
  • $\begingroup$ Although this might not hold with an instruction to access multiple storage cells at once instantly. $\endgroup$ Jan 14 at 21:44
1
$\begingroup$

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$.

$\endgroup$

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.