World's most popular travel blog for travel bloggers.

# L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?

, ,
Problem Detail:

(This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich):

For any k $\in \mathbb{N}$, let $w_k$ denote the concatenation of all k-bit long strings (in lexicographic order) separated by *'s (i.e, $w_k = 0^{k-2}00*0^{k-2}01*0^{k-2}10*...*1^k$). Show that the set $S = \{w_k:k\in\mathbb{N}\} \subset \{0,1,*\}$ is decidable in double-logarithmic space.

The basic idea of the solution, if my understanding of it is correct, is:

1. iterate from i to k until the structure of the input suits some $w_k$, for example $\{0,1\}^k*\{0,1\}^k*...*\{0,1\}^k$.
2. For each pair of adjacent binary numbers, make sure $b_{i+1} = b_i + 1$

According to the guideline in the book, step 2 takes space $O(log(k))$.

Why do I need $log(k)$ space to check if $b_{i+1} = b_i + 1$? Can't it be done in constant space?

###### Answered By : Yuval Filmus

Try to implement it in constant space to see what goes wrong. You need to be able to count up to $k$, which takes $O(\log k)$ space.

More formally, consider the language $$L = \{a\ast b : a,b \in \{0,1\}^k, b=a+1\}.$$ This is not a regular language, and so cannot be decided in constant space.