0
$\begingroup$

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?

  • 0
    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 (?)2012-08-15

1 Answers 1

1

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.