1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Nothing is mentioned in this survey. $\endgroup$
    – Yuval Filmus
    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

0

Reset to default

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.