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$

1 Answer 1

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$
6
  • $\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
    Commented Jun 27, 2017 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
    Commented Jun 27, 2017 at 8:25
  • $\begingroup$ You use Savitch to prove that @rus9384? $\endgroup$
    – shinzou
    Commented Jun 27, 2017 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
    Commented Jun 27, 2017 at 8:29
  • $\begingroup$ @rus9384 No, Savitch is for proving things about nondeterministic space classes; everything here is deterministic. $\endgroup$ Commented Jun 27, 2017 at 8:29

Your Answer

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

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