0
$\begingroup$

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.)

Improve this question
$\endgroup$
2
  • 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$
    – Emil Jeřábek
    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

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.