¿Para qué c es la división por c en AC0?

Supongamos que nuestra entrada es una binaria y tenemos que generar , donde es un número entero constante. Esto es solo un cambio si es una potencia de dos, pero ¿qué pasa con otros números? ¿Podemos hacerlo con un circuito de profundidad constante para cada ? ¿Qué pasa con ?⌊ x / c ⌋ c c c c = $x$$\lfloor x/c \rfloor$$c$$c$$c$$c=3$

PD. Sé que calcular es difícil, pero esto no parece estar relacionado.$x\bmod c$

La suma y resta de números binarios están en $\mathsf{AC^0}$ .

Para cualquier número constante $c$ , $x \bmod c$ es $\mathsf{AC^0}$ reducible a la división por $c$ ( $\lfloor x/c \rfloor$ ):

Se sabe que $x \bmod c$ es difícil para $\mathsf{AC^0}$ para cualquier $c$ que no sea una potencia de $2$ . Por lo tanto, $\lfloor x/c \rfloor$ es difícil para $\mathsf{AC^0}$ para cualquier $c$ que no sea una potencia de $2$ .

Como señaló Emil en los comentarios, hay una reducción fácil para el primer impar de (es decir, con ) a con entrada binaria: usamos solo bits de entrada que son múltiplos de y usamos FLT ( ). M O D c ∑ i x i mod c x i ∈ { 0 , 1 } x mod c p - 1 2 ( p - 1 ) i mod p = $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$