# Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?

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?

• The answer is presumably no in general, but that implies $\mathbf{L} \neq \mathbf{P}$, so an unconditional proof would be very challenging. – William Hoza Jan 23 '18 at 17:10
• On the other hand, the answer is trivially yes when $a <= b/2$. – William Hoza Jan 23 '18 at 17:13
• @WilliamHoza : How do you deduce $\mathbf{L} \ne \mathbf{P}$? – Timothy Chow Jan 23 '18 at 17:53
• 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}$). – William Hoza Jan 23 '18 at 18:08