1
$\begingroup$

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.

$\endgroup$

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.