# Problems solvable in time $f(n)$ but not in time $o(f(n))$

Suppose I have some (increasing, nice asymptotics) function $$f(n)$$. Does there exist a complexity theoretic problem (e.g. PATH, 3-SAT, GO etc.) that can be solved in time $$\Omega(f(n))$$ on a deterministic Turing machine. In other words is there a problem proven to be an element of $$\mathsf{DTIME}(f(n))$$, but not $$\mathsf{DTIME}(g(n))$$ for any function $$g$$ such that $$\frac{f(n)}{g(n)} \to \infty$$ as $$n \to \infty$$?

• Check out the Time Hierarchy Theorem. – Pål GD Feb 1 at 20:23
• The title of your post didn't match the body of your post. I modified it to reflect your post. If you're also interested in the question in the original title, please ask it separately. – Yuval Filmus Feb 2 at 9:22

Consider the language of all binary words which consist only of zeroes. It can be decided on a deterministic Turing machine in time $$O(n)$$, but not in time $$o(n)$$.
For general time-constructible functions $$f(n)$$, the time hierarchy theorem shows that the problem of deciding whether a Turing machine halts in time $$f(n)$$ can be solved in time $$O(f(n)\log f(n))$$ but not in time $$o(f(n))$$. It is not known how to eliminate this logarithmic gap in general.