Pour quoi c est la division par c dans AC0?

Supposons que notre entrée soit un binaire $x$et que nous sortir ⌊ x / c $\lfloor x/c \rfloor$ , où $c$ est un entier constant. Ce n'est qu'un changement si $c$ est une puissance de deux, mais qu'en est-il des autres nombres? Pouvons-nous le faire avec un circuit à profondeur constante pour chaque $c$ ? Et $c=3$ ?

$x\bmod c$

L'addition et la soustraction de nombres binaires sont dans$\mathsf{AC^0}$ .

Pour tout nombre constant , est réductible à la division par ( ): $c$$x \bmod c$$\mathsf{AC^0}$$c$$\lfloor x/c \rfloor$

On sait que est difficile pour pour tout qui n'est pas une puissance de . Ainsi est difficile pour pour tout qui n'est pas une puissance de .$x \bmod c$$\mathsf{AC^0}$$c$$2$$\lfloor x/c \rfloor$$\mathsf{AC^0}$$c$$2$

Comme l'a noté Emil dans les commentaires il y a une réduction facile pour premier impair de (qui est, avec ) pour avec entrée binaire: nous utilisons uniquement des bits d'entrée qui sont des multiples de et utilisons FLT ( ). $c$$\mathit{MOD}_c$$\sum_ix_i\bmod c$$x_i\in\{0,1\}$$x\bmod c$$p-1$$2^{(p-1)i} \bmod p = 1$