Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

we know that $\mathrm{DTIME}\left(o\left(\frac{f(n)}{\log(f(n))}\right)\right)$ is a subset of $\mathrm{DTIME}(f(n))$

but what can we say about $\mathrm{DTIME}{ \left(o\left(\frac{f(n)}{ (\log f(n) )^{1/2}}\right) \right) } $ in relation to $\mathrm{DTIME}(f(n))$

is it also a subset of it? are they equal?

share|cite|improve this question
Do you understand why $\mathrm{DTIME}\left(o\left(\frac{f(n)}{\log(f(n))}\right)\right)$ is a subset of $\mathrm{DTIME}(f(n))$? If so, have you tried applying similar reasoning to your question? If not, don't you think you should try to understand that first? – MJD Aug 15 '12 at 18:26
I've been trying to understand it all day without much success. my (wrong) intuition keeps getting in the way and telling me that as long as the left side is o(f(n)) we have a strict subset - which seems to be wrong, --my question is about it begin a 'strict' subset - as for it being a 'just' a subset it is clear for me--. Digging in Sipser's "intro to theory of computation" i find that o(f(n)/log(n)) is the tightest limit known so far - which leads me to say that the answer to the above question is- that it is a subset though it isn't clear if it is strict (?) – yellow Aug 15 '12 at 20:13
up vote 1 down vote accepted

It is a subset trivially by their definition, even stronger: $\mathsf{DTime(o(f))} \subseteq \mathsf{DTime(O(f))}$. This is because $o(f) \subseteq O(f)$.

However the properness of inclusion is not correct. In fact there are functions $f$ which the proper inclusion doesn't hold even for $o(f/\lg f)$. (The hierarchy theorem uses the fact that $f$ is time-constructible function, otherwise the theorem does not hold and they can be equal.)

Obtaining a stronger version of the hierarchy theorem (under the same assumptions for the the hierarchy theorem) is a long open problem in complexity theory. The diagonalization result separating the classes is based on the universal simulation results and the best known simulation results need that $\lg$ factor increase in time. AFAIK, it is not known if the simulation can be done more efficiently. If it can be done more efficiently then we can obtain stronger versions of hierarchy theorem.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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