3
$\begingroup$

In Language with $\log \log n$ space complexity?, the following non-regular language is described:

$$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$

where $b(i)$ is the $k$-bit binary representation of $i$. This can evidently be computed in $\log \log n$ space, where $n$ is the length of the string, using the typical TM with input-output tapes.

This is apparently a common example used in complexity theory, however I would like some clarification on the method of calculation -- the answer given is very unclear and differs from the method defined in the reported source.

  1. In the answer given, it says we do the check only when $m$ is smaller than the width of the first block. Am I misunderstanding this? If we do this, we never check the MSB of each representation, so for example the string $10\# 11 \# 10 \# 11$ would be accepted since it never checks $m=2$.

  2. Do we check if the $m$ least significant bits form a counter modulo $m$, or modulo $2^m$? The lecture cited checks the ending modulo $2^m$, but the answer says modulo $m$. Wouldn't having a counter that goes up to $2^m$ take $m$ space which is already too much space ($m = O(\log n)$)? If we're supposed to make the counter modulo $m$, how do we take binary numbers modulo $m$ while still satisfying the space requirement? If $m$ is a power of two we can just do addition with overflow, but what about when it's not?I don't see an obvious, space-efficient algorithm for doing this in general.

  3. Furthermore, even if we can do this in the given space, I don't see why the method taking modulo $m$ decides the language. For example, I can give you $00 \# 11 \# 10 \# 11$ and the LSBs form a counter "modulo $1$" and the two LSBs form a counter modulo $2$.

If anyone can clear up my questions that would be greatly appreciated. I think it's likely that there's just one thing I'm fundamentally misunderstanding about the presentation here which is causing everything else to not make any sense.

$\endgroup$
3
$\begingroup$

The trick here is to forget about the details as stated in the answer, and think about what would make the claim correct.

If $k$ were known, you could verify that the input is indeed $b(0)\#\cdots\#b(2^k-1)$ as follows: (below, a word is stuff between adjacent sharp signs)

  1. The first word is $0^k$.
  2. For any two contiguous words $x,y$, it holds that $y=x+1$.
  3. The last word is $1^k$.

This can be accomplished in space $O(k)$.

Unfortunately, we don't know $k$ in advance, and even if we did, it's not necessarily the case that $k = O(\log \log n)$ – there could be much less than $2^k-1$ words. Therefore we use a slightly different approach. Let $K$ be the length of the first word. For each $t \leq K$, we verify the following:

  1. The first word ends with $0^t$.
  2. For any two contiguous words $x,y$, the $t$-bit suffixes $x',y'$ satisfy $y'=x'+1$ modulo $2^t$.
  3. The last word ends with $1^t$.

If these tests pass for all $t \leq K$, then we accept the word. The $t$th test can only pass if the input is at least $(t+1)2^t-1$ symbols long and uses only $O(\log t)$ space, and this implies that the algorithm uses $O(\log\log n)$ space.

$\endgroup$
  • $\begingroup$ What's the algorithm to check that something forms a counter modulo $2^t$ only using $\log t$ extra space? $\endgroup$ – user99185 Oct 11 '16 at 14:00
  • $\begingroup$ It's an exercise. The idea is that it takes $\log t$ bits in order to count up to $t$. $\endgroup$ – Yuval Filmus Oct 11 '16 at 15:07

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.