Untuk apa c dibagi dengan c di AC0?

Misalkan input kita adalah biner dan kita harus menampilkan , di mana adalah bilangan bulat konstan. Ini hanya pergeseran jika adalah kekuatan dua, tetapi bagaimana dengan angka lainnya? Bisakah kita melakukannya dengan sirkuit kedalaman konstan untuk setiap ? Bagaimana dengan ?⌊ x / c ⌋ c c c c = $x$$\lfloor x/c \rfloor$$c$$c$$c$$c=3$

ps. Saya tahu bahwa komputasi sulit, tetapi ini tampaknya tidak berhubungan.$x\bmod c$

Penambahan dan pengurangan angka biner ada di $\mathsf{AC^0}$ .

Untuk bilangan konstan $c$ , $x \bmod c$ adalah $\mathsf{AC^0}$ dapat direduksi menjadi pembagian dengan $c$ ( $\lfloor x/c \rfloor$ ):

Diketahui bahwa $x \bmod c$ sulit untuk $\mathsf{AC^0}$ untuk setiap $c$ yang bukan kekuatan $2$ . Jadi $\lfloor x/c \rfloor$ sulit untuk $\mathsf{AC^0}$ untuk setiap $c$ yang bukan kekuatan $2$ .

Sebagaimana dicatat oleh Emil di komentar ada pengurangan mudah bagi aneh perdana dari (yaitu, dengan ) untuk dengan input biner: kami hanya menggunakan bit input yang merupakan kelipatan dan menggunakan 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$