Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can we do it with a constant depth circuit for every $c$? What about $c=3$?

ps. I know that computing $x\bmod c$ is hard, but this seems unrelated.


1 Answer 1


Addition and subtraction of binary numbers are in $\mathsf{AC^0}$.

For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}}) $$

It is known that $x \bmod c$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$. Thus $\lfloor x/c \rfloor$ is hard for $\mathsf{AC^0}$ for any $c$ which is not a power of $2$.

As noted by Emil in the comments there is an easy reduction for odd prime $c$ from $\mathit{MOD}_c$ (that is, $\sum_ix_i\bmod c$ with $x_i\in\{0,1\}$) to $x\bmod c$ with binary input: we use only input bits which are multiples of $p-1$ and use FLT ($2^{(p-1)i} \bmod p = 1$).

  • $\begingroup$ The same argument applies to any $c$ which is not a power of 2. $\endgroup$ Commented Dec 2, 2014 at 23:33
  • 4
    $\begingroup$ That $x\bmod c$ is not AC^0 for other $c$ is easy to show: for instance, we can assume $c=p$ is an odd prime, and then you can reduce MOD_p to it by using every $(p-1)$th bit. Or you can apply the Barrington-Thérien classification: it's a regular language, and its syntactic monoid is a nontrivial group. $\endgroup$ Commented Dec 2, 2014 at 23:42
  • $\begingroup$ @Emil Jerabek: Thanks, this was exactly the help i needed :) $\endgroup$
    – daniello
    Commented Dec 2, 2014 at 23:52

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.