Time hierarchy theorem states that $DTIME\bigg(o\Big(\frac{f(n)}{\log n}\Big)\bigg)\subsetneq DTIME\big(f(n)\big)$.

However space hierarchy theorem is stricter in that point since it states $SPACE\big(o(f(n))\big)\subsetneq SPACE(f(n))$. Is the same result suspected for deterministic time hierarchy?

I think I can show that $DTIME\big(o(f(n))\big)\subsetneq DTIME(f(n))$ if $f(n)\in O(n)$ but what about other functions?

  • 1
    $\begingroup$ Nothing is mentioned in this survey. $\endgroup$ Aug 24, 2017 at 9:44
  • $\begingroup$ If $f(n) = BB(n^2)$ and $g(n) = BB(n)$ (where $BB$ is the busy beaver function), then $g(n) = o(f(n) / \log n)$ but $DTIME(g(n)) = DTIME(f(n)) = R$. Usually, one adds some kind of constructability assumption to the time bounds to avoid these corner cases. The time hierarchy theorems assumes time-constructability. $\endgroup$
    – Yonatan N
    Nov 6, 2018 at 0:51
  • $\begingroup$ @YonatanN, $DTIME(g(n))\subsetneq DTIME(f(n)) \subsetneq R$ (or can I compute $BB(n^2)$ in $O(BB(n))$ time?). I don't know why do you equate a fraction of recursive functions with the class of all of them. $\endgroup$
    – rus9384
    Nov 6, 2018 at 6:14
  • $\begingroup$ The Busy Beaver function $BB(n)$ diagonalizes over all Turing machine to ensure that it a grows faster (in an asymptotic sense) than every computable function. One way to compute a function $f:\mathbb{N} \rightarrow \mathbb{N}$ may be to simulate a Turing machine $M$ that on input $x$ halts after $f(x)$ steps, and count the number of steps that $M$ takes until it halts. Thus, $BB$ grows faster than every possible tight running time upper bound. Consequently, every recursive function is in $\mathrm{DTIME}(BB(n))$. The time hierarchy doesn't work here because you can't simulate $BB(n)$ steps. $\endgroup$
    – Yonatan N
    Nov 6, 2018 at 8:42


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.