2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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