2
$\begingroup$

(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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "You need to be able to count up to k, which takes O(logk) space." That made it clear, thank you! $\endgroup$ – ranys Jul 31 '16 at 19:26

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.