1
$\begingroup$

I am trying to understand what book is saying:

Let $S(n) \leq log(n). Then$ $$DTIME(T(n)) \subseteq DSPACE(T(n))$$ $$NTIME(T(n)) \subseteq NSPACE(T(n))$$ $$DSPACE(S(n)) \subseteq DTIME(2^{O(S(n))})$$ $$NSPACE(S(n)) \subseteq NTIME(2^{O(S(n))})$$

Book gives a proof of that. But I cannot understand what $\subseteq$ means in relation to languages that have turing machines that perform smth in certain time or space bounds. Like I cannot wrap my brain around it.

Can someone help to clarify it?

Thank you!

$\endgroup$

1 Answer 1

3
$\begingroup$

Every complexity class is really just a set of languages. For example, $NSPACE(T(n))$ is the set of all languages that are decidable by some non-deterministic Turing machine using space $O(T(n))$. So $NTIME(T(n)) \subseteq NSPACE(T(n))$ just means that for any language $L$, if it is decidable by some non-deterministic Turing machine using time $O(T(n))$, then it is also decidable by some non-deterministic Turing machine using space $O(T(n))$, or equivalently, if $L \in NTIME(T(n))$, then also $L \in NSPACE(T(n))$.

$\endgroup$
2
  • $\begingroup$ Why it is inclusive subset, why not proper subset? $\endgroup$
    – YanyongXu
    Commented Sep 24, 2015 at 18:40
  • $\begingroup$ @YanyongXu I don't know about these complexity classes in particular, but sometimes it is simply because we don't know. The famous is example is of course that $P \subseteq NP$. Is it the case that $P \subset NP$? If you can prove that, you will earn a lot of prizes. $\endgroup$
    – mrp
    Commented Sep 24, 2015 at 19:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .