I wondered if anyone knew the complexity of the following problem 'Iterated Parity' (that has come up looking at the Grigorchuk group word problem).

Define the mapping $\phi : \{0,1\}^* \rightarrow \{0,1\}^*$ as follows. Let $w \in \{0,1\}^*$ be a prefix of an input, and let $a \in \{0,1\}$ be the symbol that comes after $w$. Then $\phi$ maps $a$ to 0 if $a = 0$ and the number of 1's in $w$ is even, and $\phi$ maps $a$ to 1 if $a = 0$ and the number of 1's in $w$ is odd. And $\phi$ maps $a$ to the empty string if $a$ is 1.

For example $\phi(010110) = 011$.

Define $\phi^k = \phi (\phi^{k-1} (x) )$

As input you are given a string $x \in \{0,1\}^n$, and a parameter k. The problem is determining if $\phi^k(x)$ has an even number of 1s or an odd number.

For k constant, this is just basically parity so its in $NC1$. For general k, an easy upper bound is $NC^2$. An upper bound of logspace holds as well. Can we say anything stronger about this problem? It would surprise me if this problem was in $NC1$ though I guess it might be possible. I lean towards hardness for logspace but I'm not sure how to show that.


Your Answer

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

Browse other questions tagged or ask your own question.