Po co c jest dzieleniem przez cw AC0?

Załóżmy, że nasze dane wejściowe są binarne i musimy wyprowadzić , gdzie jest jakąś stałą liczbą całkowitą. To tylko zmiana, jeśli jest potęgą dwóch, ale co z innymi liczbami? Czy możemy to zrobić z obwodem o stałej głębokości dla każdego ? Co z ? $x$ $\lfloor x/c \rfloor$ $c$ $c$ $c$ $c=3$

ps. Wiem, że obliczenie jest trudne, ale wydaje się to niezwiązane. $x\bmod c$

cc.complexity-theory circuit-complexity ac0

— domotorp
źródło

Dodawanie i odejmowanie liczb binarnych jest w $\mathsf{AC^0}$ .

Dla dowolnej stałej liczby , oznacza redukowalne do dzielenia przez ( ): $c$ $x \bmod c$ $\mathsf{AC^0}$ $c$ $\lfloor x/c \rfloor$

x mod do = x - (\overset{do czasy}{\overset{⏞}{⌊ x / do ⌋ + \dots + ⌊ x / do ⌋}})

$x \bmod c = x - (\overbrace{\lfloor x/c \rfloor + \cdots + \lfloor x/c \rfloor}^{c \text{ times}})$

Wiadomo, że jest trudne dla dla dowolnego który nie jest potęgą . Zatem jest trudne dla dla dowolnego który nie jest potęgą . $x \bmod c$ $\mathsf{AC^0}$ $c$ $2$ $\lfloor x/c \rfloor$ $\mathsf{AC^0}$ $c$ $2$

Jak zauważył Emil uwagi jest łatwo redukcji dla nieparzystej głównego z (czyli z ) do z wejścia binarne: my używaj tylko bitów wejściowych, które są wielokrotnościami i używaj 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$

— Daniello
źródło

Ten sam argument dotyczy każdego

który nie jest potęgą 2.

c

$c$

— Emil Jeřábek

To, że

nie jest AC ^ 0 dla innych

jest łatwe do wykazania: na przykład możemy założyć, że

jest nieparzystą liczbą pierwszą, a następnie można zredukować MOD_p do niego, używając każdego

bitu. Możesz też zastosować klasyfikację Barringtona-Thériena: jest to zwykły język, a jego składniowy monoid jest nietrywialną grupą.

x mod c

$x\bmod c$

c

$c$

c = p

$c=p$

(p - 1)

$(p-1)$

— Emil Jeřábek,

@Emil Jerabek: Dzięki, to była dokładnie taka pomoc, jakiej potrzebowałem :)

— daniello