<p>In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.</p>

<h2>Q3:</h2>

<p>Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon&gt;0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...</p>

<p>To continue with examples of fully time-constructible functions, one can prove that if $f_1$ and $f_2$ are fully time-constructible, then $f_1+f_2$, $f_1f_2$, $f_1^{f_2}$ and $f_1\circ f_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.</p>

<p>It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).</p>

<p>Let us also comment the definition from <a href="http://en.wikipedia.org/wiki/Constructible_function" rel="nofollow">Wikipedia article</a>: <em>A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time.</em>  We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.</p>

<h2>Q1:</h2>

<p>This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function
$$f(n)=\left\{\begin{array}{ll}
  8n+2  &amp; \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
  8n+1 &amp; \mbox{else}
 \end{array}
\right.$$</p>

<p>I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:</p>

<ul>
<li>on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time</li>
<li>then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.</li>
<li>accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.</li>
</ul>

<p>Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.</p>

<p>We can make  $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:</p>

<ul>
<li>on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done. </li>
<li>if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.</li>
</ul>

<p>Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.</p>

<p>The following algorithm solves $L$:</p>

<ul>
<li>on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.</li>
<li>compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.</li>
</ul>

<p>This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$. </p>

CC BY-SA 3.0
2013-01-14T16:37:57.650Z
Very nice! [padding to make the comment box happy]
Emil Jeřábek
CC BY-SA 3.0
2013-01-14T20:35:36.163Z
A very similar idea to the one presented in the answer to the question Q1 is also used [here](http://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science/16092#16092).
David G
CC BY-SA 3.0
2013-01-14T10:54:36.740Z
2013-01-20T20:54:46.050Z
2013-01-20T20:54:46.050Z
David G
<p>We say that a function <span class="math-container">$f:\mathbb{N}\rightarrow\mathbb{N}$</span> is <em>time-constructible</em>, if there exists a deterministic multi-tape Turing machine <span class="math-container">$M$</span> that on all inputs of length <span class="math-container">$n$</span> makes at most <span class="math-container">$f(n)$</span> steps and for each <span class="math-container">$n$</span> there exists some input of length <span class="math-container">$n$</span> on which <span class="math-container">$M$</span> makes exacltly <span class="math-container">$f(n)$</span> steps.</p>
<p>We say that a function <span class="math-container">$f:\mathbb{N}\rightarrow\mathbb{N}$</span> is <em>fully time-constructible</em>, if there exists a deterministic multi-tape Turing machine <span class="math-container">$M$</span> that on all inputs of length <span class="math-container">$n$</span> makes exactly <span class="math-container">$f(n)$</span> steps.</p>
<blockquote>
<p>Q1: Does there exist a function which is time-construcible and not fully time-constructible?</p>
</blockquote>
<p>The answer is yes (see <a href="https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085">this answer</a>), if <span class="math-container">$EXP-TIME \neq NEXP-TIME$</span>. Can the condition for &quot;yes&quot; be strengthened to <span class="math-container">$P\neq NP$</span>? Can &quot;yes&quot; be proven?</p>
<blockquote>
<p>Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?</p>
<p>Q3: What are the &quot;provable&quot; reasons for believing that all nice functions are fully time-constructible?</p>
</blockquote>
<p>The paper<br />
<em>Kojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)</em><br />
partially answers Q3. The partial summary and upgrade of it is in <a href="https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085">this answer</a>. I take Q3 as answered.</p>
<p>Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See <a href="https://cstheory.stackexchange.com/questions/16101/real-time-countable-vs-fully-time-constructible">this question</a> for more.</p>

CC BY-SA 3.0
2013-01-09T16:39:13.557Z
Curious -- could you point me to a reference for these definitions? I am not familiar with constructible functions, and I can't find these definitions online (it's also not obvious to me whether they're equivalent to *e.g.* the [wikipedia](http://en.wikipedia.org/wiki/Constructible_function) ones).
usul
CC BY-SA 3.0
2013-01-10T11:04:47.867Z
@usul The reference is:

J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science, 1979

The same definition can be found here:
http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html
David G
<cc.complexity-theory><time-complexity><terminology>
Equivalent definitions of time constructibility
David G
# Equivalent definitions of time constructibility

(Asked by: username_0 on 2013-01-08)

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is *time-constructible*, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ steps and for each $n$ there exists some input of length $n$ on which $M$ makes exacltly $f(n)$ steps.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is *fully time-constructible*, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps.

> Q1: Does there exist a function which is time-construcible and not fully time-constructible?

The answer is yes (see [this answer](https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085)), if $EXP-TIME \neq NEXP-TIME$. Can the condition for "yes" be strengthened to $P\neq NP$? Can "yes" be proven?

> Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?
>
> Q3: What are the "provable" reasons for believing that all nice functions are fully time-constructible?

The paper  
*Kojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)*  
partially answers Q3. The partial summary and upgrade of it is in [this answer](https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085). I take Q3 as answered.

Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See [this question](https://cstheory.stackexchange.com/questions/16101/real-time-countable-vs-fully-time-constructible) for more.

**Tags:** cc.complexity-theory, time-complexity, terminology

> **Comments:**
> **username_1**: Curious -- could you point me to a reference for these definitions? I am not familiar with constructible functions, and I can't find these definitions online (it's also not obvious to me whether they're equivalent to *e.g.* the [wikipedia](http://en.wikipedia.org/wiki/Constructible_function) ones).  
> **username_0**: @username_1 The reference is:  J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science, 1979  The same definition can be found here: http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese2.html  

---

## 1 answers

### Answer by username_0 on 2013-01-14. Score: 6

In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.

## Q3:

Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon>0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...

To continue with examples of fully time-constructible functions, one can prove that if $f\_1$ and $f\_2$ are fully time-constructible, then $f\_1+f\_2$, $f\_1f\_2$, $f\_1^{f\_2}$ and $f\_1\circ f\_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.

It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).

Let us also comment the definition from [Wikipedia article](http://en.wikipedia.org/wiki/Constructible_function): *A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time.* We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.

## Q1:

This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^\*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function
$$f(n)=\left\{\begin{array}{ll}
8n+2 & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
8n+1 & \mbox{else}
\end{array}
\right.$$

I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:

* on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
* then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
* accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.

Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.

We can make $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:

* on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
* if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.

Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.

The following algorithm solves $L$:

* on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
* compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.

> **Comments:**
> **username_2**: Very nice! [padding to make the comment box happy]  
> **username_0**: A very similar idea to the one presented in the answer to the question Q1 is also used [here](http://cstheory.stackexchange.com/questions/3616/common-false-beliefs-in-theoretical-computer-science/16092#16092).  

---

