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

5

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.

  • 1
    How is $n$ presented to $A$? Shouldn't $A$ be a language in DTIME($2^{n^2}$) but not DTIME($2^n$)?2012-07-04
1

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.

  • 1
    Your function TUC is not computable, let alone time-constructible. In fact non-computable function is trivially not time-constructible. What is hard is to come up with a computable, but not time-constructible function.2017-09-12