[Solved]: Space complexity below $\log\log$

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^{c\cdot 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 $i\neq 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(\log\log 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