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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jan 23, 2018 at 17:10
  • 4
    $\begingroup$ On the other hand, the answer is trivially yes when $a <= b/2$. $\endgroup$
    – William Hoza
    Commented Jan 23, 2018 at 17:13
  • 1
    $\begingroup$ @WilliamHoza : How do you deduce $\mathbf{L} \ne \mathbf{P}$? $\endgroup$
    – Timothy Chow
    Commented Jan 23, 2018 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
    Commented Jan 23, 2018 at 18:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.