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

11

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

пс. Я знаю, что вычислить сложно, но это кажется не связанным.xmodc

domotorp
источник

Ответы:

16

Сложение и вычитание двоичных чисел находятся в AC0 .

Для любого числа постоянной , является сводится к делению на ( ): х мод с С 0 с х / с х мод с = х - ( с  раз х / с + + х / с )cxmodcAC0cx/c

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

Известно, что трудно для для любого который не является степенью . Таким образом, трудно для для любого который не является степенью .A C 0 c 2 x / c A C 0 c 2xmodcAC0c2x/cAC0c2

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

Даниелло
источник
Тот же аргумент применим к любому который не является степенью 2.c
Эмиль Йержабек
4
То, что не является AC ^ 0 для других , легко показать: например, мы можем предположить, что - нечетное простое число, а затем вы можете уменьшить MOD_p до него, используя каждый -й бит , Или вы можете применить классификацию Баррингтона-Териена: это обычный язык, и его синтаксический моноид является нетривиальной группой. c c = p ( p - 1 )xmodccc=p(p1)
Эмиль Йержабек
@ Эмиль Джерабек: Спасибо, это была именно та помощь, в которой я нуждался :)
Даниелло