Para que c é divisão por c em AC0?

Suponha que nossa entrada seja um binário e tenhamos que produzir ⌊ x / c ⌋ , onde c é um número inteiro constante. Isso é apenas uma mudança se c é uma potência de dois, mas e os outros números? Podemos fazer isso com um circuito de profundidade constante para cada c ? E quanto a c = 3 ?$x$$\lfloor x/c \rfloor$$c$$c$$c$$c=3$

$x\bmod c$

A adição e subtração de números binários estão em$\mathsf{AC^0}$ .

Para qualquer número constante , é redutível à divisão por ( ): $c$$x \bmod c$$\mathsf{AC^0}$$c$$\lfloor x/c \rfloor$

Sabe-se que é difícil para para qualquer que não seja uma potência de . Portanto, é difícil para para qualquer que não seja uma potência de .$x \bmod c$$\mathsf{AC^0}$$c$$2$$\lfloor x/c \rfloor$$\mathsf{AC^0}$$c$$2$

Como observado por Emil nos comentários, há uma redução fácil para o número primo ímpar de (ou seja, com ) para com entrada binária: usamos apenas bits de entrada que são múltiplos de e usamos 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$