Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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

Asked By : user14864

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23721

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback