2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Apr 13 '14 at 9:08
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Looks like you are taking $B-A$. $\endgroup$ – saadtaame Apr 13 '14 at 22:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.