Para que c é divisão por c em AC0?

11

Suponha que nossa entrada seja um binário e tenhamos que produzir x / c , onde c é um número inteiro constante. Isso é apenas uma mudança se c é uma potência de dois, mas e os outros números? Podemos fazer isso com um circuito de profundidade constante para cada c ? E quanto a c = 3 ?xx/ccccc=3

xmodc

domotorp
fonte

Respostas:

16

A adição e subtração de números binários estão emAC0 .

Para qualquer número constante , é redutível à divisão por ( ): cxmodcAC0cx/c

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

Sabe-se que é difícil para para qualquer que não seja uma potência de . Portanto, é difícil para para qualquer que não seja uma potência de .xmodcAC0c2x/cAC0c2

Como observado por Emil nos comentários, há uma redução fácil para o número primo ímpar de (ou seja, com ) para com entrada binária: usamos apenas bits de entrada que são múltiplos de e usamos FLT ( ). cMODciximodcxi{0,1}xmodcp12(p1)imodp=1

daniello
fonte
O mesmo argumento se aplica a qualquer que não seja um poder de 2. #c
960 Emil Jeřábek 3.0
4
Que não é AC ^ 0 para outro é fácil de mostrar: por exemplo, podemos assumir que é um primo ímpar e, em seguida, você pode reduzir MOD_p a ele usando cada bit . Ou você pode aplicar a classificação de Barrington-Thérien: é uma linguagem comum e seu monóide sintático é um grupo não trivial. xmodccc=p(p1)
Emil Jeřábek 3.0
@Emil Jerabek: Obrigado, isso era exatamente a ajuda que precisava :)
Daniello