Für was ist c Division durch c in AC0?

Angenommen, unsere Eingabe ist ein binäres und wir müssen ausgeben , wobei eine konstante ganze Zahl ist. Dies ist nur eine Verschiebung, wenn eine Zweierpotenz ist, aber was ist mit anderen Zahlen? Können wir es mit einem Stromkreis mit konstanter Tiefe für jedes ? Was ist mit ?≤ x / c ≤ c c c c = $x$$\lfloor x/c \rfloor$$c$$c$$c$$c=3$

ps. Ich weiß, dass das Berechnen von schwierig ist, aber dies scheint nichts damit zu tun zu haben.$x\bmod c$

Addition und Subtraktion von Binärzahlen erfolgen in $\mathsf{AC^0}$ .

Für jede konstante Zahl $c$ , $x \bmod c$ ist $\mathsf{AC^0}$ reduzierbar auf Division durch $c$ ( $\lfloor x/c \rfloor$ ):

Es ist bekannt, dass $x \bmod c$ für $\mathsf{AC^0}$ für jedes $c$ das keine Potenz von 2 ist, schwierig ist $2$. Daher ist $\lfloor x/c \rfloor$ für $\mathsf{AC^0}$ für jedes $c$ das keine Potenz von 2 ist, schwierig $2$.

Wie von Emil in den Kommentaren bemerkt, gibt es eine einfache Reduktion für ungerade Primzahlen von ( mit ) auf mit Binäreingang: Wir verwenden nur Eingangsbits, die Vielfache von und verwenden 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$