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.

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?

share|improve this question
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".) –  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
1  
What is the difference from another question of yours? –  Tsuyoshi Ito Aug 3 '11 at 0:43
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. –  Tsuyoshi Ito Aug 3 '11 at 12:43

2 Answers 2

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.

share|improve this answer
    
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.

share|improve this answer

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.