2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – shinzou Jun 27 '17 at 7:52
  • 1
    $\begingroup$ @kuhaku, it depends on $f(n)$. If it is polynomial, then - yes, it will imply $\mathsf{P = NP}$. $\endgroup$ – rus9384 Jun 27 '17 at 8:25
  • $\begingroup$ You use Savitch to prove that @rus9384? $\endgroup$ – shinzou Jun 27 '17 at 8:26
  • $\begingroup$ @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. $\endgroup$ – rus9384 Jun 27 '17 at 8:29
  • $\begingroup$ @rus9384 No, Savitch is for proving things about nondeterministic space classes; everything here is deterministic. $\endgroup$ – David Richerby Jun 27 '17 at 8:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.