Relationship between SPACE(t(n)) and DTIME(t(n))

Asked 11 months ago

Viewed 48 times

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes

We have that

$DTIME(n)\subseteq SPACE(n) \subseteq NSPACE(n) \subseteq DTIME(2^n)$

and by the Time Hierarchy Theorem,

$DTIME(n)\subseteq DTIME(n^2) \subseteq DTIME(2^n) \subseteq DTIME(2^{2^n})$

So, my gut feeling is that

$SPACE(\log^2n) \subseteq DTIME(n) \subseteq DTIME(n^2) \subseteq SPACE(n/\log n) \subseteq SPACE(n) \subseteq DTIME(2^n) \subseteq DTIME(2^{2^n})$

However, I'm not sure where $SPACE(\log^2 n)$ and $SPACE(n/\log n)$ fit in. I think that this follows from the Space Hierachy Theorem -

$${SPACE}\left(o(f(n))\right) \subsetneq SPACE(f(n))$$

Is there another theorem or result I could review to justify my proposed order?

asked Mar 18 '19 at 4:47

Axion004

1012 bronze badges

$\begingroup$ "and by the Time Hierarchy Theorem, [...]" The time hierarchy theorem only tells you those are proper inclusions. The inclusions themselves follow directly from the definition of the time (and space) complexities (i.e., any TM with time complexity $t$ is included in $\mathbf{TIME}(t')$ if $t < t'$). $\endgroup$ – dkaeae Mar 18 '19 at 10:26
$\begingroup$ Also, I am not sure your inclusion $\mathbf{SPACE}(n) \subseteq \mathbf{DTIME}(2^n)$ is correct. A TM using space $f(n)$ must run in time $f(n) 2^{f(n)}$, so for $f(n) = n$ we get a bound of $n 2^n$, not $2^n$. Possibly you are thinking about $\mathbf{DTIME}(2^{O(n)}) = \mathbf{E}$, which is a (much) larger class. $\endgroup$ – dkaeae Mar 18 '19 at 10:34
$\begingroup$ Why do you think $\mathsf{SPACE}(\log^2 n)$ is contained in $\mathsf{DTIME}(n)$? $\endgroup$ – Yuval Filmus Mar 18 '19 at 11:35
$\begingroup$ I thought that $SPACE(n) \subseteq DTIME(2^n)$ because $SPACE(n) \subset DTIME(2^{O(n)})$. Although, I likely interpreted this wrong as you suggested that this would mean $SPACE(n) \subseteq DTIME(n2^n)$, not $SPACE(n) \subseteq DTIME(2^n)$. I think that $SPACE(log^2 n)$ is contained in $DTIME(n)$ by the same property above ($SPACE(n) \subset DTIME(2^{O(n)})$). I think I am misinterpreting what this property means. $\endgroup$ – Axion004 Mar 18 '19 at 14:11

add a comment |

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

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