1

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!

YanyongXu
  • 81

1 Answers1

3

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))$.

mrp
  • 5,086
  • Why it is inclusive subset, why not proper subset? – YanyongXu Sep 24 '15 at 18:40
  • @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. – mrp Sep 24 '15 at 19:03