10
$\begingroup$

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))?

$\endgroup$
  • 3
    $\begingroup$ 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" $\endgroup$ – Ryan Williams Sep 5 '10 at 18:00
  • $\begingroup$ 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^*. $\endgroup$ – Tsuyoshi Ito Sep 6 '10 at 0:39
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 6 '10 at 0:57
  • 2
    $\begingroup$ 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. $\endgroup$ – Tian Liu Sep 6 '10 at 13:55
  • $\begingroup$ 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. $\endgroup$ – Tian Liu Sep 6 '10 at 14:06
6
$\begingroup$

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 or Papadimitriou's for more information. (The latter uses the term "proper complexity function" to refer to one that is both time and space constructible.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tian Liu Sep 6 '10 at 14:14
  • $\begingroup$ 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. $\endgroup$ – Yitz Sep 7 '10 at 10:26
  • $\begingroup$ It is just a typo. $\endgroup$ – Tsuyoshi Ito Sep 7 '10 at 14:11
  • $\begingroup$ Sorry Yitz. I fixed the typo. $\endgroup$ – M.S. Dousti Sep 20 '10 at 17:44
4
$\begingroup$

$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)$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tian Liu Sep 5 '10 at 23:42
  • $\begingroup$ @Tian, $f(n)= n$ is space-constructable but not time-constructable function. $\endgroup$ – Mohammad Al-Turkistany Sep 6 '10 at 11:13
  • $\begingroup$ 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 ? $\endgroup$ – Tian Liu Sep 6 '10 at 13:45
2
$\begingroup$

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 uses the same idea.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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