Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jul 12 '11 at 18:45

This question came from our site for theoretical computer scientists and researchers in related fields.

1  
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. –  Tyson Williams Jul 12 '11 at 15:31
1  
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)$? –  Kaveh Jul 12 '11 at 15:40
    
The scope of cstheory is defined as research-level tcs as explained in cstheory FAQ. –  Kaveh Jul 12 '11 at 18:57
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
1  
with your logic, why f = n and f = c are not time constructible? I also have difficulty to grasp the concept. –  user15409 Sep 1 '11 at 18:47
    
@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. –  Zev Chonoles Sep 1 '11 at 18:52
1  
@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. –  Kaveh Sep 1 '11 at 18:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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