9
$\begingroup$

A function $T: \mathbb N \rightarrow \mathbb N$ is time constructible if $T(n) \geq n$ and there is a $TM$ $M$ that computes the function $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ in time $T(n)$. ($\llcorner T(\vert x\vert) \lrcorner$ denotes the binary representation of the number $T(\vert x\vert)$.)

Examples for time-constructible functions are $n$, $nlogn$, $n^2$, $2^n$. Time bounds that are not time constructible can lead to anomalous results.

--Arora, Barak.

This is the definition of time-constructible functions in Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak.

It is hard to find valid examples of non-time-constructible functions. $f(n)=c$ is an example of a non-time-constructible function. What more (sophisticated) examples are out there?

  • 1
    The book clearly mentions $n$ as an example of a time-constructible function. Why do you claim it is non-time-constructible? (Also, please be more clear about the reference: include the full title perhaps. Not everyone would know "the CC book".)2011-08-02
  • 0
    Oh, sorry, you are right! I found the examples of non-time-constructible functions on [these](http://cl-informatik.uibk.ac.at/teaching/ss07/alth/ohp/week5-2x2.pdf) slides. My intention was to get the discussion started.2011-08-02
  • 0
    I believe the Inverse Ackermann function is not-time constructible.2011-08-02
  • 1
    What is the difference from [another question of yours](http://math.stackexchange.com/questions/51082/definition-of-time-constructible-function)?2011-08-03
  • 0
    There is no significant difference but the focus here is on concrete examples since they seem really hard to pinpoint. My previous question was predominantly about an intuitive definition.2011-08-03
  • 1
    You basically ignored the answer to your other question and posted part of the question as a separate entry. You even hid the fact that it was part of your previous question. Neither of these actions is nice. Please take the minimum responsibility for asking a question if you want your question to be treated seriously.2011-08-03
  • 0
    I'm sorry, but I did not ignore my previous question. In fact, I'm studying the answer still, but I can't accept it since I don't understand it. Actually, you are being not nice on this here. Please avoid elongating on off-topic and meta subjects. I'm still interested in answeres to my previous and to this question. I did not hide anything, I'm well aware everybody can track my question and answer history.2011-08-03
  • 0
    Well, if you think that what you are doing is fine, I have nothing to say. I will leave this question to those who are willing to answer.2011-08-03

2 Answers 2