Time constructible function in Hierarchy Theorem

Question

I read the definition of time constructible function and saw that $f(n)$ should be at least $O(nlogn)$. I could not understand why $f(n)$ should be greater than $O(nlogn)$. Also I could not understand why we need constructible functions in proving the hierarchy theorem?

Answer 1

I follow the beginning of the proof from Sipser's Introduction to the Theory of Computation. I will try to point out the differences between Space Hierarchy and Time Hierarchy.

We are going to construct a machine $M$ that works in $O(f(n))$ time, but not in $o(f(n)/\log f(n)$ time. The machine $M$ works as follows:

On an input $w$ of length $n$, if $w$ is of the form $<T>10^*$, it simulates the work of $T$ on $w$ for $f(n)/\log(n)$ steps. It rejects if $T$ accepts and accepts if $T$ rejects (to make sure that $M$ is different from $T$). If $T$ doesn't halt after $f(n)/\log(n)$ steps, reject.

This is where you need that $f(n)$ is constructible - you need to be able to compute $f(n)$ in order to know for how long you should simulate $T$ (actually, you need to compute $f(n)/\log n$).

This is also where the difference between space and time comes from - it takes some time to compute $f(n)$, which you cannot use later anymore (in the case of Space Hierarchy, you can compute $f(n)$ and reuse the space you needed for this computation). By making sure that $f(n)$ is constructible, it can be computed in time $O(f(n))$ so it doesn't affect the overall running time of $M$.

When performing the computation of $M$, you need to make two things: simulate $T$ on $w$ AND keep track of how many steps you performed. This AND is where the $\log$ comes from - because after simulating a step of $T$ you need to subtract $1$ from the counter. In general, subtracting $1$ from a number $k$ takes $\log k$ steps. Hence if the counter had size about $f(n)$, you would need $O(f(n)\cdot \log f(n))$ time for the computation of $M$.

Because you are simulating only $f(n)/\log f(n)$ steps, the counter has size about $f(n)/\log f(n)$ so you need $O(\frac{f(n)}{\log f(n)}\cdot\log\frac{f(n)}{\log f(n)})=O(f(n))$ steps.