First let's have some definition (you can find these in any complexity's textbook)

Theorem. [Gap Theorem] There is a computable time bound $t(n)$ such that DTIME[ $t(n)$ ]= DTIME[ $r(t(n))$ ] for any computable function $r$.

This theorem says that even if you have more time resources, then you cannot do more. We have another theorem that says.

Theorem. [Time Hierarchy Theorem (THT)] if f and g are time-constructible functions and f(n)=o(g(n)), then DTIME[ $f(n)$ ] $\subsetneq$ DTIME[ $g(n)$ ].

It is clear that if $f$ and $g$ are not time-constructible, then THT wouldn't hold. Time-constructible ensures that we read the whole input in the input tape of the TM.

Question: If $f$ and $g$ are not time-constructible, why then THT cannot hold? What makes THT cannot hold even if f and g are not time-constructible?


  • 1
    $\begingroup$ Take a look at the proof of the time hierarchy theorem. $\endgroup$ – Yuval Filmus Apr 17 at 17:37
  • $\begingroup$ Thank you Yuval. Is it because UTM runs on at most $O(n log n)$ steps? because I took an example such that $f(n)=\log n$ and $g(n)=n$ (Now, we have $f(n)$ is not time-constructible). Now if I run UTM U with input $M$ and $<M>$ in $g(n)$ steps (this is the first step of the simulation in the THT and M is a TM such that $L(M) \in$ DTIME[$g(n)$]), then U will take n log n where $n=|<M>|$ and this is more than $g(n)=n$ steps. Therefore, the simulation will always interrupt and return reject. So we will never have a diagonalization method in this case. Is this true Yuval? $\endgroup$ – user777 Apr 18 at 12:19
  • 1
    $\begingroup$ Presumably the proof of the time hierarchy theorem uses time-constructibility somewhere. $\endgroup$ – Yuval Filmus Apr 18 at 14:02
  • $\begingroup$ I don't understand Yuval! So are you saying that my idea is not true and I should rethink again? $\endgroup$ – user777 Apr 18 at 14:11
  • 1
    $\begingroup$ I'm saying that the reason that the time hierarchy theorem requires time-constructibility, is that this assumption is used somewhere in the proof. $\endgroup$ – Yuval Filmus Apr 18 at 14:12

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.