Por que limites inferiores para circuitos booleanos não implica circuitos aritméticos limites inferiores

10

Minha pergunta é: por que limites inferiores para circuitos booleanos de profundidade 3 com portas "e" e "xor" para determinantes não implicam os mesmos limites inferiores para circuitos aritméticos sobre ?Z

O que há de errado com o seguinte argumento: Seja um determinante de cálculo do circuito aritmético, e tomando todas as variáveis ​​mod 2, obteremos o determinante de cálculo do circuito booleano. C

Alguém
fonte

Respostas:

12

Para circuitos aritméticos acima de seu argumento é exatamente correto. O mesmo argumento funciona para circuitos aritméticos sobre Q, que não usam nenhuma fração a / b onde b é par.ZQa/bb

QRCFqq2

Z

Zab=¬(¬a¬b)

fRφ:RSφfSfSfSSfR

Joshua Grochow
fonte
b
3
ba/bQab1(mod2)
Isso significa que provar algum tipo de teorema como divisão de von (isto é, que você não precisa dividir por dois) implicará em limites inferiores do circuito sobre C?
Klim
@Klim: Não. O problema é que um circuito em C ainda pode usar constantes irracionais (ou mesmo não reais), que você ainda não pode usar o "mod 2."
Joshua Grochow #