Mi pregunta es ¿por qué los límites inferiores para los circuitos booleanos de profundidad 3 con puertas "y" y "xor" para determinante no implican los mismos límites inferiores para los circuitos aritméticos sobre ?
Lo que está mal con el siguiente argumento: Sea un determinante calculador del circuito aritmético y luego tomando todas las variables mod 2 obtendremos el determinante calculador del circuito booleano.
Para los circuitos aritméticos sobre su argumento es exactamente correcto. El mismo argumento funciona para los circuitos aritméticos sobre que no usan ninguna fracción donde es par.
Sin embargo, el argumento ya no funciona si habla de circuitos aritméticos sobre otros anillos, tales como: circuitos aritméticos generales sobre (es decir, sin la restricción anterior), R , campos de números algebraicos, C o campos finitos F q con q ≠ 2 .
(Esta es esencialmente la misma razón por la que en la geometría algebraica menudo se considera la llamada "característica mixta", en lugar de la característica cero).
Sin embargo, la profundidad de 3 Boolean reducir los límites para circuitos con {AND, OR, NOT} son menos fácilmente relacionados para bajar los límites para circuitos aritméticos más de . (Sí, {AND, XOR} es una base completa, pero por lo general la profundidad de 3 circuitos sobre {AND, OR, NOT} considera que NO tiene puertas libres, mientras que al implementar NOT con XOR está usando una puerta XOR, que realmente cuenta De manera similar, aunque a ∨ b = ¬ ( ¬ a ∧ ¬ b ) , cuando implementa esta única puerta OR con AND y XOR, obtiene un pequeño dispositivo de profundidad 3.)
La afirmación general es: sea un polinomio con coeficientes en un anillo R , y suponga que φ : R → S es un homomorfismo en anillo. Mediante la aplicación φ a cada coeficiente de f se obtiene un polinomio con coeficientes en S , que voy a denotan f S . Entonces, un límite inferior para calcular f S por circuitos aritméticos S implica el mismo límite inferior para calcular f por circuitos aritméticos R.