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))?
Asked
Active
Viewed 1,379 times
11
-
3http://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 Sep 05 '10 at 18:00
-
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 Sep 06 '10 at 00:39
-
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 Sep 06 '10 at 00:57
-
2Thanks 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 Sep 06 '10 at 13:55
-
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 Sep 06 '10 at 14:06
-
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 Sep 06 '10 at 16:23
-
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 Sep 06 '10 at 16:27
3 Answers
7
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.)
Sadeq Dousti
- 16,479
- 9
- 69
- 152
-
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 Sep 06 '10 at 14:14
-
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 Sep 07 '10 at 10:26
-
-
4
$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)$.
Yuval Filmus
- 14,445
- 1
- 48
- 92
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
-
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 Sep 05 '10 at 23:42
-
@Tian, $f(n)= n$ is space-constructable but not time-constructable function. – Mohammad Al-Turkistany Sep 06 '10 at 11:13
-
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 Sep 06 '10 at 13:45
2
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.
