Problem Detail: Show that for $l(n) = log log n$, it holds that $text{DSPACE}(o(l)) = text{DSPACE}(O(1))$. It’s well known fact in Space Complexity, but how to show it explicitly?
Asked By : com
Answered By : A.Schulz
So here is the main idea behind this fact. Let us denote by $C$ all possible configuration of the $l(n)$-space bounded TM. Notice that $|C|le 2^{ccdot l(n)}$, where $c$ is a constant depending on $M$. We assume that the input tape is a two-way tape. Let $w$ be a word of size $n$, such that for all smaller words $u$ we have $l(w)>l(u)$. When the head moves from position $i$ to position $i+1$ on the input tape, or vice versa, we record the current configuration of the computation in the crossing sequence $C_i$. Assume we have $ineq j$ with $C_i=C_j$. Then we define as $w’$ the word obtained from $w$ by deleting everything between the characters number $i$ and $j$. We observe that $w’$ is a shorter word which uses the same amount of space. Contradiction, there is no such $w$. If $l(n)in o(loglog n)$ then you have $o(log n)$ configurations and $o(n)$ crossing sequences. Hence two crossing sequences are the same. Notice that if your input tape is 1-way, then even with $o(log n)$ space you are doomed.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7372