14
$\begingroup$

What would be an intuitive notion of time-constructible functions ? Is there a function which is not time-constructible?

In my own words I would say a function is time-constructible when:

  1. it is computable on a TM and
  2. it is computed in time which itself calculates.

So, $2^n$ might be time-constructible if there is a TM calculating $2^n$ (for any given n) and the calculation ends in at most $2^n$ time (steps, seconds, some other time measure, etc.).

I'm reading the book CC by Arora and Barak. I got stuck on page 16 where the definition for Time-constructible functions is given, which, in my words says:

"A function f is time-constructible when there is a TM that computes f in f(n) time."

For me, this is about writing a program (for a TM) that computes a value f(n) where the calculation itself may not exceed f(n) time which is the value to be calculated by the TM. So there is some kind of tricky self-reference.

I would like to know where the notion of time and space complexity comes from, i.e. what it is good for, and some counterexample for it - some function that is not time constructible. This would help grasp the concept better, which seems to me to be really fundamental for all the rest (in the book).


I'm having difficulties understanding this concept and its rational, since it is kind of self-referential; it is defining itself by means of its own output. Some examples and counterexamples would be really useful. Thank you.

$\endgroup$
4
  • 1
    $\begingroup$ Ryan Williams gave an answer to another question in which he talks about why time-constructible functions are necessary for many of the hierarchy theorems. $\endgroup$
    – Tyson Williams
    Jul 12, 2011 at 15:31
  • 1
    $\begingroup$ This doesn't look like a research-level question, probably more suitable for Math.SE. The basic use of time-constructibility (and space-constructibility) is to clock machines, i.e. we want to simulate a machine only for $t(n)$ steps on an input of length $n$, only using $O(t(n))$ steps. To do this, we need to compute the value of $t(n)$ in time $O(t(n))$. ps: there is no self-reference in the concept: (for a fixed function $t$,) can we compute $t$ in time $O(t)$? $\endgroup$
    – Kaveh
    Jul 12, 2011 at 15:40
  • $\begingroup$ The scope of cstheory is defined as research-level tcs as explained in cstheory FAQ. $\endgroup$
    – Kaveh
    Jul 12, 2011 at 18:57
  • $\begingroup$ Is T(n) = log(log(n)) a time constructible function? $\endgroup$
    – alienCoder
    Sep 13, 2015 at 10:53

1 Answer 1

12
$\begingroup$

The basic use of time-constructibility (and space-constructibility) is to clock the time a machines runs (or space it uses), i.e. we want to simulate a machine only for $t(n)$ steps on an input of length $n$, only using $O(t(n))$ steps. To do this, we need to compute the value of $t(n)$ in time $O(t(n))$. If $t(n)$ cannot be computed in time $O(t(n))$ the total running time of simulation will not be $O(n)$.

An example is when we want to prove a hierarchy theorem. We need to simulate all machines in the smaller class in the time bound of the larger class.

There is no self-reference. Fix a function, e.g. $n^2$. This is function, we are not talking about how it is computed. Now the question is given $n$, we want to compute the value of $n^2$ (both input and output in binary). What is the complexity of this problem? Well, it is $O(n^2)$. So $n^2$ is time-constructible. The function $n^2$ is used twice (once as function we want to compute and once as the time bound) but it is not a self-reference.


Update:

Is there a function which is not time-constructible?

Yes, there are. E.g. any non-computable function is not time constructible. But I think you mean are there computable functions which are not time constructible? The answer is still yes, but giving examples is not very easy because most functions that we deal with in practice turn out to be time constructible.

$\endgroup$
5
  • 1
    $\begingroup$ with your logic, why f = n and f = c are not time constructible? I also have difficulty to grasp the concept. $\endgroup$
    – user15409
    Sep 1, 2011 at 18:47
  • 1
    $\begingroup$ @eureka: I have converted your answer to a comment. Answers should be reserved for posts that answer the question. But because you do not have 50 reputation points yet, you can only comment on your own questions and answers. So, you didn't do anything wrong; the "add comment" button will only appear for you once you gain 50 points. Here is an explanation of reputation points. $\endgroup$ Sep 1, 2011 at 18:52
  • 1
    $\begingroup$ @eureka, $f(n)=n$ is time-constructible. In fact, you can compute the first one even in time $O(\log n)$. $f(n)=c$ is also time constructible, ignore the input and write $c$ which will take $\log c$ steps. $\endgroup$
    – Kaveh
    Sep 1, 2011 at 18:55
  • $\begingroup$ @panny I am pretty sure $\log n $ is not time-constructable. You wouldn't be able to even read the input within $\log n$. $\endgroup$ Sep 15, 2018 at 13:15
  • 1
    $\begingroup$ @AbhijeetMelkani Does the following prove that log n is time-constructible? Given input x of length log n, use a second tape as counter and increment after reading each bit of x, so log n times. Incrementation takes time equal to the current length of the counter, so first bit is visited log n times, second bit log n / 2 times, and i-th bit log n / (2*^*i) times. Since the counter will eventually be of length loglog n, the total number of visits is log n * (1+1/2+1/4+...+1/(log n)) up to a factor of 2 (for going back and forth), which is O(log n). $\endgroup$
    – Antonio AN
    Mar 22, 2020 at 10:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.