Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Why is TIME(n log (log n)) \ TIME(n) = ∅?

, ,
Problem Detail:

In my computation book by Sipser, he says that since every language that can be decided in time \$o(n \log n)\$ is regular, then that can be used to show \$TIME(n \log (\log n))\setminus TIME(n)\$ must be the empty set. Can anyone show me why this is?

both \$TIME(n\log(\log n))\$ and \$TIME(n)\$ are regular. I think that only means we can subtract the two sets and the result will still be regular. I just dont understand how its possible to subtract the collection of \$O(n\log(\log n))\$ time TM decidable languages from the collection of \$O(n)\$ time TM decidable languages and get the empty set. These two collections are not equal so I feel like there will be something left over

The quick explanation is that

\$TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[o(n\log n)]\$, and therefore \$TIME[o(n\log n)]=REG\$.

Similarly:

\$TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG\subseteq TIME[n]\subseteq TIME[n\log \log n]\$, so \$TIME[n\log\log n]=REG\$

But I think this is not the point you are missing.

You say that \$TIME[n\log \log n]\$ is regular. This is not exact. When we say that something is regular, we mean that it is a language \$L\subseteq \Sigma^*\$, which is regular (i.e. can be recognized by a DFA).

The class REG is not a language, but a set of languages. That is, \$REG\subseteq 2^{\Sigma^*}\$. Similarly, \$TIME[f(n)]\subseteq 2^{\Sigma^*}\$ for every function \$f\$. These are all classes of languages.

Since we have that \$TIME[n\log\log n]\subseteq TIME[o(n\log n)]\subseteq REG\$, then \$REG\setminus TIME[n\log\log n]=\emptyset\$. This follows from the simple property that if \$A\subseteq B\$, then \$A\setminus B=\emptyset\$.