<p>A function $T \colon \mathbb{N} \to \mathbb{N}$ is time constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto T(|x|)$ in time $O(T(n))$.</p>

<p>A function $S \colon \mathbb{N} \to \mathbb{N}$ is space constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto S(|x|)$ in space $O(S(n))$.</p>

<p>Some texts require that time/space constructible functions be non-decreasing. Some texts require the time constructible functions satisfy $T(n)\ge n$, and the space constructible functions satisfy $S(n)\ge \log n$. Some texts do not make use of the $O(\cdot)$ notation in the definition.</p>

<p>Anyway, it is easy to show that every "ordinary" function $f$, satisfying $f(n)\ge \log n$ and $f(n) = o(n)$ is space constructible, but not time constructible.</p>

<p>The constructibility problem is not directly related to possible separation between complexity classes DTIME(f(n)) and SPACE(f(n)). However, the statement of time and space hierarchy theorems incorporates the constructibility. For example:</p>

<p><b>Time Hierarchy Theorem</b>
If $f$, $g$ are time-constructible functions satisfying $f(n)\log f(n) = o(g(n))$, then
$\mathbf{DTIME}(f(n))$ is a <i>proper</i> subset of $\mathbf{DTIME}(g(n))$.</p>

<p>See <a href="http://rads.stackoverflow.com/amzn/click/0521424267">Arora &amp; Barak's book</a> or <a href="http://rads.stackoverflow.com/amzn/click/0201530821">Papadimitriou's</a> for more information. (The latter uses the term "proper complexity function" to refer to one that is both time and space constructible.)</p>

CC BY-SA 2.5
2010-09-06T14:14:19.573Z
Thanks. I prefer the definition that a function is time/space-constructible if there is a Turing machine which runs in exact  that steps/tape squares. Of course, by the linear time/space speed-up theorems, this is equivalent to your/textbook definitions.
Tian Liu
CC BY-SA 2.5
2010-09-07T10:26:52.787Z
Sadeq, your definitions for "time constructible" and "space constructible" are word-for-word identical. Are you saying that these are just two different names for exactly the same concept? If not, perhaps you should fix your definitions.
Yitz
CC BY-SA 2.5
2010-09-07T14:11:53.130Z
It is just a typo.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T17:44:20.697Z
Sorry Yitz. I fixed the typo.
Sadeq Dousti
CC BY-SA 2.5
2010-09-06T01:13:48.813Z
2010-09-20T17:42:43.760Z
2010-09-20T17:42:43.760Z
Sadeq Dousti
<p>$f(n)=\log n$ is space constructable but not time constructable. The reason is that you can map $1^n$ to the binary representation in space $O(\log n)$ but not in time $O(\log n)$.</p>

CC BY-SA 2.5
2010-09-05T23:42:31.053Z
Thanks to the comment and answer. But can you show a function f(n)which is at least linear, that is, f(n)>=n, for the separation ? It seems that a time-constructible function can not be less than n for an apparent reason: have to read all input bits, otherwise an adversary argument can show that the function is not correctly computed.
Tian Liu
CC BY-SA 2.5
2010-09-06T11:13:14.147Z
@Tian, $f(n)= n$ is space-constructable but not time-constructable function.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-06T13:45:43.083Z
Thanks again, but are you assume that the read-head on input tape is initially located at left to the first bit of input? in that case, to detect the last bit of input, the head has to move to right n+1 times until meet the first blank after input. Then $f(n)=n+1$ is time-constructible. So please give a "non-trival" separation by a function f(n)>=n+1 ?
Tian Liu
CC BY-SA 3.0
2010-09-05T11:05:02.217Z
2013-01-20T22:40:27.530Z
2013-01-20T22:40:27.530Z
Mohammad Al-Turkistany
<p>If all space-constructible functions are time-constructible, then $EXP-TIME=EXP-SPACE$. To prove that (and to give an example of a non-trivial space-constructible but presumably not time-constructible function), let us take an arbitrary (possibly $EXP-SPACE-COMPLETE$) problem $L\in EXP-SPACE$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a DTM $M$ in $2^{n^k}$ space. 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>The condition can be decided in $2n$ space, thus $f$ is space-constructible. If $f$ was time constructible, then it is easy to see that we could solve $L$ in exponential time.</p>

<p><a href="https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085">This answer</a> uses the same idea.</p>

CC BY-SA 3.0
2013-01-20T20:58:15.860Z
2013-01-20T20:58:15.860Z
2017-04-13T12:32:28.167Z
David G
<p>Show a function $f(n)$ which is space-constructible but not time-constuctible. </p>

<p>Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?</p>

CC BY-SA 2.5
2010-09-05T18:00:56.707Z
http://en.wikipedia.org/wiki/Constructible_function As far as I know, this question is unrelated to TIME(f(n)) vs SPACE(f(n)), but note these two classes *are known* to be different. Look for the articles "On Time Versus Space", "On Time Versus Space II", "On Time Versus Space III"
Ryan Williams
CC BY-SA 2.5
2010-09-06T00:39:15.467Z
A quick observation: I think that the problem is equivalent to asking whether DTIME(f(n))∩TALLY and SPACE(f(n))∩TALLY can be different for some space-constructible function f(n), where TALLY is the class of languages which are subsets of 1^*.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T00:57:04.317Z
Oops, they may not be equivalent.  Here is a proof of one direction.  If there exists a language L={1^n | n∈S} ∈ TALLY∩(SPACE(f(n))∖DTIME(f(n))) for some space-constructible function f(n), then both f(n) and f(n)+χ_S(n) (where χ_S(n) is the characteristic function of S) are space-constructible but not both are time-constructible, and therefore at least one of them is a space-constructible but not time-constructible function.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T13:55:02.377Z
Thanks to Ryan, by your comment I know that TIME(f(n)) is contained in SPACE(f(n)/log f(n)) by Hopcroft et al, and the latter is properly contained in SPACE(f(n)) by the space hierarchy theorem.
Tian Liu
CC BY-SA 2.5
2010-09-06T14:06:57.840Z
Thanks to Tsuyoshi, very clever ideas, if both f(n) and f(n)+χ_S(n) are time-constructible, then we can decide whether n∈S in at most f(n)+1 time, thus L∈TALLY ∩ DTIME(f(n)), a contradiction. but can your constructions be called "explict"? which one is not time-constructible, f(n) or f(n)+χ_S(n)? by "explicit" if I mean that we can decide the value f(n) for all n, then your construction is explict.
Tian Liu
CC BY-SA 2.5
2010-09-06T16:23:45.837Z
Hmm, a good point. If we know that f(n) is time-constructible, then f(n)+χ_S(n) is an explicit example of space-constructible but not time-constructible functions.  If we only know that f(n) is space-constructible but do not know whether f(n) is time-constructible or not, then the argument does not give an explicit example as you point out.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T16:27:57.700Z
If we drop the “explicit” part, is it known that there exists a space-constructible function f(n)≥n which is not time-constructible?
Tsuyoshi Ito
<cc.complexity-theory><space-bounded><separation>
An explicit separation between time-constructibility and space-constructibility?
Tian Liu
# An explicit separation between time-constructibility and space-constructibility?

(Asked by: username_0 on 2010-09-05)

Show a function $f(n)$ which is space-constructible but not time-constuctible.

Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?

**Tags:** cc.complexity-theory, space-bounded, separation

> **Comments:**
> **username_1**: http://en.wikipedia.org/wiki/Constructible_function As far as I know, this question is unrelated to TIME(f(n)) vs SPACE(f(n)), but note these two classes *are known* to be different. Look for the articles "On Time Versus Space", "On Time Versus Space II", "On Time Versus Space III"  
> **username_2**: A quick observation: I think that the problem is equivalent to asking whether DTIME(f(n))∩TALLY and SPACE(f(n))∩TALLY can be different for some space-constructible function f(n), where TALLY is the class of languages which are subsets of 1^*.  
> **username_2**: Oops, they may not be equivalent.  Here is a proof of one direction.  If there exists a language L={1^n | n∈S} ∈ TALLY∩(SPACE(f(n))∖DTIME(f(n))) for some space-constructible function f(n), then both f(n) and f(n)+χ_S(n) (where χ_S(n) is the characteristic function of S) are space-constructible but not both are time-constructible, and therefore at least one of them is a space-constructible but not time-constructible function.  
> **username_0**: Thanks to Ryan, by your comment I know that TIME(f(n)) is contained in SPACE(f(n)/log f(n)) by Hopcroft et al, and the latter is properly contained in SPACE(f(n)) by the space hierarchy theorem.  
> **username_0**: Thanks to Tsuyoshi, very clever ideas, if both f(n) and f(n)+χ_S(n) are time-constructible, then we can decide whether n∈S in at most f(n)+1 time, thus L∈TALLY ∩ DTIME(f(n)), a contradiction. but can your constructions be called "explict"? which one is not time-constructible, f(n) or f(n)+χ_S(n)? by "explicit" if I mean that we can decide the value f(n) for all n, then your construction is explict.  
> **username_2**: Hmm, a good point. If we know that f(n) is time-constructible, then f(n)+χ_S(n) is an explicit example of space-constructible but not time-constructible functions.  If we only know that f(n) is space-constructible but do not know whether f(n) is time-constructible or not, then the argument does not give an explicit example as you point out.  
> **username_2**: If we drop the “explicit” part, is it known that there exists a space-constructible function f(n)≥n which is not time-constructible?  

---

## 3 answers

### Answer by username_3 on 2010-09-06. Score: 8

A function $T \colon \mathbb{N} \to \mathbb{N}$ is time constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto T(|x|)$ in time $O(T(n))$.

A function $S \colon \mathbb{N} \to \mathbb{N}$ is space constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto S(|x|)$ in space $O(S(n))$.

Some texts require that time/space constructible functions be non-decreasing. Some texts require the time constructible functions satisfy $T(n)\ge n$, and the space constructible functions satisfy $S(n)\ge \log n$. Some texts do not make use of the $O(\cdot)$ notation in the definition.

Anyway, it is easy to show that every "ordinary" function $f$, satisfying $f(n)\ge \log n$ and $f(n) = o(n)$ is space constructible, but not time constructible.

The constructibility problem is not directly related to possible separation between complexity classes DTIME(f(n)) and SPACE(f(n)). However, the statement of time and space hierarchy theorems incorporates the constructibility. For example:

**Time Hierarchy Theorem**
If $f$, $g$ are time-constructible functions satisfying $f(n)\log f(n) = o(g(n))$, then
$\mathbf{DTIME}(f(n))$ is a *proper* subset of $\mathbf{DTIME}(g(n))$.

See [Arora & Barak's book](http://rads.stackoverflow.com/amzn/click/0521424267) or [Papadimitriou's](http://rads.stackoverflow.com/amzn/click/0201530821) for more information. (The latter uses the term "proper complexity function" to refer to one that is both time and space constructible.)

> **Comments:**
> **username_0**: Thanks. I prefer the definition that a function is time/space-constructible if there is a Turing machine which runs in exact  that steps/tape squares. Of course, by the linear time/space speed-up theorems, this is equivalent to your/textbook definitions.  
> **username_4**: Sadeq, your definitions for "time constructible" and "space constructible" are word-for-word identical. Are you saying that these are just two different names for exactly the same concept? If not, perhaps you should fix your definitions.  
> **username_2**: It is just a typo.  
> **username_3**: Sorry username_4. I fixed the typo.  

---

### Answer by username_5 on 2010-09-05. Score: 5

$f(n)=\log n$ is space constructable but not time constructable. The reason is that you can map $1^n$ to the binary representation in space $O(\log n)$ but not in time $O(\log n)$.

> **Comments:**
> **username_0**: Thanks to the comment and answer. But can you show a function f(n)which is at least linear, that is, f(n)>=n, for the separation ? It seems that a time-constructible function can not be less than n for an apparent reason: have to read all input bits, otherwise an adversary argument can show that the function is not correctly computed.  
> **username_5**: @Tian, $f(n)= n$ is space-constructable but not time-constructable function.  
> **username_0**: Thanks again, but are you assume that the read-head on input tape is initially located at left to the first bit of input? in that case, to detect the last bit of input, the head has to move to right n+1 times until meet the first blank after input. Then $f(n)=n+1$ is time-constructible. So please give a "non-trival" separation by a function f(n)>=n+1 ?  

---

### Answer by username_6 on 2013-01-20. Score: 3

If all space-constructible functions are time-constructible, then $EXP-TIME=EXP-SPACE$. To prove that (and to give an example of a non-trivial space-constructible but presumably not time-constructible function), let us take an arbitrary (possibly $EXP-SPACE-COMPLETE$) problem $L\in EXP-SPACE$, $L\subseteq\{0,1\}^\*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a DTM $M$ in $2^{n^k}$ space. 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.$$

The condition can be decided in $2n$ space, thus $f$ is space-constructible. If $f$ was time constructible, then it is easy to see that we could solve $L$ in exponential time.

[This answer](https://cstheory.stackexchange.com/questions/15019/equivalent-definitions-of-time-constructibility/16085#16085) uses the same idea.


---

