# Can we get a better time hierarchy theorem?

The time hierarchy theorem states that

$DTIME(f(n)) \neq DTIME(f(n)\log(f(n)))$

(Let me acknowledge that this statement isn't 100 percent accurate because f must be "time constructible" and potentially other things that I'm missing)

If we were to take some function f, we can consider

$DTIME(f(n)) \subset DTIME(f(n)\sqrt{\log(f(n))})\subset DTIME(f(n)\log(f(n)))$

Where we know that at least one of these inclusions is strict. Do we know of examples where one of these inclusions isn't?

In general we might want to prove that $DTIME(f(n)) \neq DTIME(f(n)g(f(n)))$ for a function $g$ which is as small as possible. Do we have better upper bounds on $g$ (like $g(n) = \log\log n$)? do we have non-trivial lower bounds on $g$ in the form of some (time constructible) $f$ for which $DTIME(f(n) = DTIME(f(n)g(f(n)))$?

• The time hierarchy theorem as stated is the strongest time hierarchy theorem currently known. However, there is no reason to suspect that a stronger statement is not true. – Yuval Filmus Jan 6 '17 at 18:57

To improve this theorem, you need faster Universal Turing Machine. The $log(n)$ overhead of the currently fastest simulation technique seems to be unavoidable, especially for large enough time bounds, since with more time resource the simulated TM can do crazy things that the UTM cannot assume some regular property to do the simulation faster.