# Is $DSPACE(f) \subseteq DTIME(f)$ always?

Is $DSPACE(f) \subseteq DTIME(f)$ always?

For example, if we have a language $A\in DSPACE(log^2(n))$ can we say that $A\in P$ (and subsequently in NP and coNP) since $DSPACE(log^2(n))\subseteq DSPACE(n^3) \subseteq DTIME(n^3)$?

I know about $DTIME(f) \subseteq DSPACE(f) \subseteq DTIME(2^{O(f)})$ but $DTIME(2^{O(f)})$ is too big in this case.

We don't know that $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$ is ever true and we suspect that it's never true.

A Turing machine that uses space $f(n)$ can run for $2^{O(f(n))}$ steps without getting stuck in an infinite loop, so it should be able to do much more than a Turing machine that can only run for $f(n)$ steps. As you've observed, if $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$, then $\mathrm{DSPACE}[f(n)]=\mathrm{DTIME}[f(n)]$ and we have no reason to think that would ever be true for reasonable functions.

• So it's an open question? is it related to P=NP? like if $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$ then P=NP? – shinzou Jun 27 '17 at 7:52
• @kuhaku, it depends on $f(n)$. If it is polynomial, then - yes, it will imply $\mathsf{P = NP}$. – rus9384 Jun 27 '17 at 8:25
• You use Savitch to prove that @rus9384? – shinzou Jun 27 '17 at 8:26
• @kuhaku, padding argument, and the fact that $\mathsf{NTIME(f(n)) \subseteq DSPACE(f(n))}$. I'm not sure if last is true for every $f(n))$, but surely it is for polynomials and larger functions. – rus9384 Jun 27 '17 at 8:29
• @rus9384 No, Savitch is for proving things about nondeterministic space classes; everything here is deterministic. – David Richerby Jun 27 '17 at 8:29