1
$\begingroup$

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$?

$\endgroup$
2
  • 1
    $\begingroup$ Check out the Time Hierarchy Theorem. $\endgroup$ – Pål GD Feb 1 at 20:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 2 at 9:22
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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