<p>The title question arose in the course of discussing a <a href="https://mathoverflow.net/questions/290312/can-more-polynomial-time-compensate-for-less-polynomial-memory">question on MathOverflow</a>.  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 <i>in the other direction</i>.  But once we limit the time budget of the left-hand side to $n^a$, I'm no longer sure what we can say.</p>

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

CC BY-SA 3.0
2018-01-23T17:10:41.103Z
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
CC BY-SA 3.0
2018-01-23T17:13:58.193Z
On the other hand, the answer is trivially yes when $a <= b/2$.
William Hoza
CC BY-SA 3.0
2018-01-23T17:53:41.667Z
@WilliamHoza : How do you deduce $\mathbf{L} \ne \mathbf{P}$?
Timothy Chow
CC BY-SA 3.0
2018-01-23T18:08:16.627Z
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
<cc.complexity-theory><space-time-tradeoff>
Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?
Timothy Chow
# Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?

(Asked by: username_0 on 2018-01-23)

The title question arose in the course of discussing a [question on MathOverflow](https://mathoverflow.net/questions/290312/can-more-polynomial-time-compensate-for-less-polynomial-memory). 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?

**Tags:** cc.complexity-theory, space-time-tradeoff

> **Comments:**
> **username_1**: The answer is presumably no in general, but that implies $\mathbf{L} \neq \mathbf{P}$, so an unconditional proof would be very challenging.  
> **username_1**: On the other hand, the answer is trivially yes when $a <= b/2$.  
> **username_0**: @WilliamHoza : How do you deduce $\mathbf{L} \ne \mathbf{P}$?  
> **username_1**: 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}$).  

---

## 0 answers

