# Is there an additive time hierarchy theorem?

I would like something like this to be true:

Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), there is a language in $TIME[f(n)]$ that is not in $TIME[f(n) - g(n)]$.

Is anything like this known? Can this be proven under any reasonable assumptions? Would this have any interesting consequences?

By $TIME[f(n)]$, I mean the set of problems solved by a Turing machine that halts in exactly $f(n)$ steps or less - not to be confused with $O(f(n))$ or less, in which case the conjecture is trivially false when $f(n) >> g(n)$.

• Separations are by diagonalization and require simulation of the smaller class, and simulation requires asymptotically dominating the smaller function. Furthermore, I think what you want would contradict speed up theorems. – Kaveh Jun 9 '14 at 3:25

I don't see the need for your clarification, since through linear speed-up those sets are exactly the same. It is clear why you need to avoid using asymptotics, since $f(n)-g(n)$ and $f(n)$ are asymptotically the same, but not using asymptotics doesn't somehow make the linear speed-up theorem not true.
Some further insight can be gained. $g(n)$ is actually $g(f(n))$,i.e. it must depend on $f(n)$ to work for all functions. Why? Suppose g(n) is non-constant. Pick $f(n) = 2 g(n)$ . Then clearly $f(n)$ and $f(n)-g(n)$ are equal by the linear speed-up theorem. If $g(n)=c$ is constant, then we can pick a non-constant $f(n)$ so that the conjecture doesn't hold.
What if we allow dependency on $f(n)$? Well then by taking the known deterministic hierarchy theorem and doing some basic arithmetic we can see that any $g(f(n))$ that is $o((1 - \frac{1}{ \log f(n)} ) f(n) )$ works. However I am not sure if just by stating the same theorem in a slightly different form opens up the possibility of some new insight.
• The speedup theorem is something I should have seen coming, but it doesn't exactly answer the spirit of the question. Perhaps I should have said that the TMs must have alphabet $\{0, 1, B\}$ to disallow this sort of trick. – GMB Jun 9 '14 at 21:06