There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a function where $\exists \epsilon > 0$ such that $\forall^{\infty} n$ $f(n) \geq (1 + \epsilon) n$.

What is the meaning/necessity of this additive epsilon term in the definition of $f$? I can't seem to find an adequate definition of why we need it here, but not for the corresponding space constructibility theorem. My intuition is that we need a little extra time to set up and run the Turing machine, so we can't 'count' exactly $f(n)$ time but rather a little more.

As a follow-up, does this mean that $f(n) = n$ is not a time constructible function? Because I was under the impression that all natural polynomial functions including linear were time constructible.

(My model of computation is a multitape Turing machine.)

  • 1
    $\begingroup$ $f(n)=n$ is time constructible all right. But the proof of the theorem presumably only works for $f(n)\ge(1+\epsilon)n$. I suppose that it is not true in general that a function computable in time $O(n)$ is computable in time $n$, which sounds like something you would in the proof (but I have not looked at it). In any case, you are misinterpreting the situation: if the theorem requires further conditions, it means these conditions are not part of the definition of time-constructible functions. $\endgroup$ Sep 10 at 6:23
  • $\begingroup$ Welcome to TCS-SE! Please, complement your question with clear references. Statements like "There is a well-known theorem" should rather be explicit references to XXX proved the theorem YYY in year ZZZZ [Reference]. $\endgroup$
    – J..y B..y
    Sep 14 at 10:43


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.