10
$\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?

$\endgroup$
8
  • 1
    $\begingroup$ 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".) $\endgroup$
    – Srivatsan
    Aug 2, 2011 at 10:14
  • $\begingroup$ 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. $\endgroup$
    – panny
    Aug 2, 2011 at 10:17
  • $\begingroup$ I believe the Inverse Ackermann function is not-time constructible. $\endgroup$
    – chazisop
    Aug 2, 2011 at 16:30
  • 1
    $\begingroup$ What is the difference from another question of yours? $\endgroup$
    – Tsuyoshi Ito
    Aug 3, 2011 at 0:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Aug 3, 2011 at 12:43

2 Answers 2

Reset to default
7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ How is $n$ presented to $A$? Shouldn't $A$ be a language in DTIME($2^{n^2}$) but not DTIME($2^n$)? $\endgroup$
    – Colin McQuillan
    Jul 4, 2012 at 0:02
  • $\begingroup$ could you elaborate on this? how does $f(n)$ prove that $n^2$ is in $n$? $\endgroup$
    – AlexH
    Nov 18, 2021 at 18:38
1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – fade2black
    Sep 12, 2017 at 10:08

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