11
$\begingroup$

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.

Improve this question
$\endgroup$
16
$\begingroup$

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$).

Improve this answer
$\endgroup$
3
  • $\begingroup$ The same argument applies to any $c$ which is not a power of 2. $\endgroup$ – Emil Jeřábek Dec 2 '14 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$ – Emil Jeřábek Dec 2 '14 at 23:42
  • $\begingroup$ @Emil Jerabek: Thanks, this was exactly the help i needed :) $\endgroup$ – daniello Dec 2 '14 at 23:52

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.