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?

$\endgroup$
  • 1
    $\begingroup$ Nothing is mentioned in this survey. $\endgroup$ – Yuval Filmus Aug 24 '17 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 '18 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 '18 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 '18 at 8:42

Your Answer

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

Browse other questions tagged or ask your own question.