9
$\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.).


EDIT:

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.

  • 0
    Is T(n) = log(log(n)) a time constructible function?2015-09-13

1 Answers 1

6

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.

  • 0
    @panny I am pretty sure $\log n $ is not time-constructable. You wouldn't be able to even read the input within $\log n$.2018-09-15