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))?
$\begingroup$
$\endgroup$
7
-
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 WilliamsCommented Sep 5, 2010 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 ItoCommented Sep 6, 2010 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 ItoCommented Sep 6, 2010 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 LiuCommented Sep 6, 2010 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 LiuCommented Sep 6, 2010 at 14:06
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
4
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.)
answered Sep 6, 2010 at 1:13
-
$\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 LiuCommented Sep 6, 2010 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$– YitzCommented Sep 7, 2010 at 10:26
-
-
$\begingroup$ Sorry Yitz. I fixed the typo. $\endgroup$ Commented Sep 20, 2010 at 17:44
$\begingroup$
$\endgroup$
3
$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)$.
answered Sep 5, 2010 at 11:05
-
$\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 LiuCommented Sep 5, 2010 at 23:42
-
$\begingroup$ @Tian, $f(n)= n$ is space-constructable but not time-constructable function. $\endgroup$ Commented Sep 6, 2010 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 LiuCommented Sep 6, 2010 at 13:45
$\begingroup$
$\endgroup$
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.
