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$

1 Answer 1

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$
1
  • $\begingroup$ "You need to be able to count up to k, which takes O(logk) space." That made it clear, thank you! $\endgroup$
    – ranys
    Commented Jul 31, 2016 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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