Для чего c деление на c в AC0?

Предположим, что наш вход является двоичным и мы должны вывести , где - некоторое постоянное целое число. Это просто сдвиг, если является степенью двойки, но как насчет других чисел? Можем ли мы сделать это с контуром постоянной глубины для каждого ? Как насчет ? $x$ $\lfloor x/c \rfloor$ $c$ $c$ $c$ $c=3$

пс. Я знаю, что вычислить сложно, но это кажется не связанным. $x\bmod c$

cc.complexity-theory circuit-complexity ac0 domotorp
источник

Сложение и вычитание двоичных чисел находятся в $\mathsf{AC^0}$ .

Для любого числа постоянной , является сводится к делению на ( ): $c$ $x \bmod c$ $\mathsf{AC^0}$ $c$ $\lfloor x/c \rfloor$

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

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

Известно, что трудно для для любого который не является степенью . Таким образом, трудно для для любого который не является степенью . $x \bmod c$ $\mathsf{AC^0}$ $c$ $2$ $\lfloor x/c \rfloor$ $\mathsf{AC^0}$ $c$ $2$

Как отметил Эмиль в комментариях, существует простое сокращение нечетного простого числа с (то есть с ) до с двоичный вход: мы используем только входные биты, кратные и используем 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$

Даниелло
источник

Тот же аргумент применим к любому который не является степенью 2.

c

$c$

Эмиль Йержабек

То, что не является AC ^ 0 для других , легко показать: например, мы можем предположить, что - нечетное простое число, а затем вы можете уменьшить MOD_p до него, используя каждый -й бит , Или вы можете применить классификацию Баррингтона-Териена: это обычный язык, и его синтаксический моноид является нетривиальной группой.

x mod c

$x\bmod c$

c

$c$

c = p

$c=p$

(p - 1)

$(p-1)$

Эмиль Йержабек

@ Эмиль Джерабек: Спасибо, это была именно та помощь, в которой я нуждался :)

Даниелло

Для чего c деление на c в AC0?

Ответы: