Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
Thank you very much for the answer, I am a little bit confused what is crossing sequence, according to wikipedia it is the sequence of the states (if it's so why $i \neq j$ with $C_i = C_j$). Could you please provide more details for the last statement with $o(\log n)$ configurations and $o(n)$ crossing sequences. – tam Dec 14 '12 at 8:33
A crossing sequence is a sequence of configurations of a TM. As explained in the answer: every time the head of the input tape moves between cell $i$ and $i+1$ you take the current configuration and append it to the sequence $C_i$. Regarding your second question. In the answer we discussed that there are $2^{cl(n)}$ configurations $C$, but since $l(n)=o(\log\log n)$ this means that you have $|C|=o(\log n)$. Now consider the number of all possible subsets of $C$, there are $2^{|C|}=o(n)$ many such subsets, hence there are $o(n)$ different crossing sequences. – A.Schulz Dec 14 '12 at 9:25
thank you for explanation, one more question, when the head move between cell $i$ and $i+1$, the current configuration goes to $C_i$, but theoretically head can move from $i$ to $i+1$ many times during the processing of TM so $C_i$ can have a lot of set. What can I say if $C_i=C_j$, I see a kind of redundancy (What can I state more formally?). Why having less that $n$ crossing sequence concludes that TM used the constant space? – tam Dec 19 '12 at 10:49
The crossing sequences are not sets, but sequences, if $C_i=C_j$ then you can cut the input between $i$ and $j$ and the computation would still fit together. Hence there is a shorter word accepted, using the same space. – A.Schulz Dec 19 '12 at 12:07

The (I think) original proof is by Hartmanis, Lewis & Stearns, conveniently available for free :).

My rough understanding of it is that it goes via equivalence to the class of regular languages in the sense that you only need a constant amount of space to decide a regular language (just whatever state it's up to, basically), so they're decidable in $DSPACE(O(1))$, but if you want to decide anything non-regular, then you need $\Omega(\log\log n)$ space, so there's an "empty" gap, even with that extra bit of space ($o(\log\log n)$), it's so tiny that you can't do anything new with it.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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