Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

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

I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich. The goal is to show that the given set $S=\left \{ w_k \mid k \in \mathbb{N} \right \}$, where $w_k$ - concatenation of all $k$-bit long strings separated by *'s is not regular and yet it is decidable in double-logarithmic space. The exercise contains guidelines, and I would like to shed the light on few sentences from guidelines in order to solve the exercise.

In the guidelines it's mentioned that

we can take advantage of of the *'s (in $w_i$) , the $i$th iteration can be implemented in space $O(\log i)$

The $i$th iteration is verifying whether $x = w_i$, which is really can be decided in $O(\log i)$ space, where $\log i$ can be used to note the position in $i$ long string, but the position in $x$ can be included in $O(\log i)$ or not?

Furthermore, on input $x \notin S$, we halt and reject after at most $\log |x|$ iterations.

It means only $\log |x|$ $w$'s from the set S will be compared to $x$. Why it is actually so?

Actually, it is slightly simpler to handle the related set $\left \{w_1**w_2**..**w_k \right \}$

Why it is actually so, and I would call it set, it is rather concatenated string.

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

Well, the set $\left \{w_1**w_2**..**w_k \right \}$ contains only one single element, but is nevertheless a set. And TM can accept only languages, which are sets of words.

Why is it slightly easier? Hmm, I would say, it is easier since you can simplify the algorithm slightly. You have one counter for $k$, and then you check, whether in the string $\cdots *x*y*\cdots$, you have $\text{bin}(y)=\text{bin}(x)+1$ on every position. You do not have to care about detecting the right $k$. Other than this, the suoer-string is longer, which gives you more space. But this effect vanishes in the big-O.

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.