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