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

11

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 = 3xx/ccccc=3

PD. Sé que calcular es difícil, pero esto no parece estar relacionado.xmodc

domotorp
fuente

Respuestas:

16

La suma y resta de números binarios están en AC0 .

Para cualquier número constante c , xmodc es AC0 reducible a la división por c ( x/c ):

xmodc=x(x/c++x/cc times)

Se sabe que xmodc es difícil para AC0 para cualquier c que no sea una potencia de 2 . Por lo tanto, x/c es difícil para AC0 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 = 1cMODciximodcxi{0,1}xmodcp12(p1)imodp=1

daniello
fuente
El mismo argumento se aplica a cualquier que no sea una potencia de 2.c
Emil Jeřábek
44
Es fácil mostrar que no es AC ^ 0 para otra : por ejemplo, podemos suponer que es un número impar impar, y luego puede reducir MOD_p usando cada bit . O puede aplicar la clasificación Barrington-Thérien: es un lenguaje regular y su monoide sintáctico es un grupo no trivial. c c = p ( p - 1 )xmodccc=p(p1)
Emil Jeřábek
@Emil Jerabek: Gracias, esta fue exactamente la ayuda que necesitaba :)
daniello