# non time constructible functions

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?

-
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".) –  Srivatsan Aug 2 '11 at 10:14
Oh, sorry, you are right! I found the examples of non-time-constructible functions on these slides. My intention was to get the discussion started. –  panny Aug 2 '11 at 10:17
I believe the Inverse Ackermann function is not-time constructible. –  chazisop Aug 2 '11 at 16:30
What is the difference from another question of yours? –  Tsuyoshi Ito Aug 3 '11 at 0:43
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. –  Tsuyoshi Ito Aug 3 '11 at 12:43

You can use the time hierarchy theorem to create a counter-example.

You know by the THT that DTIME($n$)$\subsetneq$DTIME($n^2$), so pick a language which is in DTIME($n^2$)$\backslash$DTIME($n$). For this language you have a Turing machine $A$ which decideds if a string is in the language in time $O(n^2)$ and $\omega(n)$. You can now define the following function

$f(n) = 2\cdot n+A(n)$

If it is time constructible it contradicts the THT.

-
How is $n$ presented to $A$? Shouldn't $A$ be a language in DTIME($2^{n^2}$) but not DTIME($2^n$)? –  Colin McQuillan Jul 4 '12 at 0:02

According to the definition of Arora, trigonometric functions are not good counter-examples since they are not functions from $\mathbb{N}$ to $\mathbb{N}$.

However, the function $TUC : \mathbb{N} \rightarrow \mathbb{N}$ defined by $TUC(n) = n$ if $M_n(n) \neq n$ and $TUC(n) = 2n + 1$ otherwise, is not time-constructible:

Suppose there exists $M$ that computes $TUC$ in $TUC(n)$ time, then there exist $n$ such that $M = M_n$ (cf. encoding of a Turing machine in Arora's book), but

-if $TUC(n) = n$, then $M(n) \neq n$ and so $TUC(n) \neq n$ $\rightarrow$ contradiction.

-if $TUC(n) = 2n +1$, then $M(n) = n$ and so $TUC(n) = n$ $\rightarrow$ contradiction.

Both cases end up to a contradiction so $TUC$ is not time-constructible.

-
Really? I presumed the $T(n) \ge n$ condition was sorta kinda important... –  Ｊ. Ｍ. Sep 30 '11 at 10:42
@J.M. you are right, hence a Turing machine needs atleast $n$ time to process the input. So you cannot even speak about functions which are computable in less then $n$. –  sxd Sep 30 '11 at 11:32