5
$\begingroup$

The title question arose in the course of discussing a question on MathOverflow. Obviously, from the space hierarchy theorem we know that not only is it false that $\mathrm{DSPACE}(n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$, but there is a proper inclusion in the other direction. But once we limit the time budget of the left-hand side to $n^a$, I'm no longer sure what we can say.

If the question can't be answered unconditionally, then can we answer it conditional on some standard hypothesis or relative to some oracle?

$\endgroup$
  • 6
    $\begingroup$ The answer is presumably no in general, but that implies $\mathbf{L} \neq \mathbf{P}$, so an unconditional proof would be very challenging. $\endgroup$ – William Hoza Jan 23 '18 at 17:10
  • 4
    $\begingroup$ On the other hand, the answer is trivially yes when $a <= b/2$. $\endgroup$ – William Hoza Jan 23 '18 at 17:13
  • 1
    $\begingroup$ @WilliamHoza : How do you deduce $\mathbf{L} \ne \mathbf{P}$? $\endgroup$ – Timothy Chow Jan 23 '18 at 17:53
  • 6
    $\begingroup$ Assume, say, $\mathbf{DTISP}(n^{10}, n^4) \not \subseteq \mathbf{DSPACE}(n^2)$. Then there is some language $A$ that can be decided in time $O(n^{10})$ (so $A \in \mathbf{P}$) but that cannot be decided in space $O(n^2)$ (so $A \not \in \mathbf{L}$). $\endgroup$ – William Hoza Jan 23 '18 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.