Consecuencias prácticas de

Antecedentes

Complejidad del circuito se define como el conjunto de familias de circuitos (es decir, secuencias de circuitos, una para cada tamaño de entrada) de profundidad acotada y tamaño polinomial construido utilizando el ventilador sin límites AND, OR y NOT.$AC^0$

La función de paridad con entrada de n bits es igual al XOR de los bits en la entrada.$\oplus$$n$

Uno de los primeros circuitos de límite inferior probado en complejidad de circuito es el siguiente:

[FSS81], [Ajt83]: .$\oplus \notin AC^0$

Preguntas:

Sea la clase de funciones que se pueden calcular usando circuitos electrónicos de profundidad acotada y tamaño polinómico usando partes electrónicas como transistores. (Creé el nombre E C 0 , avíseme si conoce un nombre mejor para esto).$EC^0$$EC^0$

1. ¿Podemos calcular en la práctica usando circuitos E C 0 ?$\oplus$$EC^0$

2. ¿Qué pasa con el fan-in ilimitado AND / OR? ¿Podemos calcularlos en ?$EC^0$

3. ¿El tiene ningún consecuencias prácticas? ¿ Es importante A C 0 en la práctica?$\oplus \notin AC^0$$AC^0$

4. ¿Por qué es importante para los informáticos (teóricos)?$\oplus \notin AC^0$

Nota:

Esta publicación contiene preguntas interesantes, pero OP parece negarse a hacer que la publicación sea más legible y corregir la idea errónea por alguna razón, por lo que estoy volviendo a publicar preguntas. (Sería más fácil editar la publicación original, pero actualmente no hay un acuerdo si está bien editar en gran medida la publicación de otro usuario).

Relacionado:

• Paridad y $AC^0$

• ¿Por qué no es importante la paridad en ? $AC^0$(Blog de complejidad computacional)

No soy ingeniero eléctrico, pero busco patentes en línea con respecto a los circuitos de conmutación para puertas de paridad, y todas las propuestas (encontré las patentes solo hasta fines de la década de 1970) discuten el problema del tamaño versus la profundidad. Las tres patentes que he analizado proponen soluciones de profundidad logarítmica, basadas en compuertas fanin-2. Entonces la respuesta a su primera pregunta es posiblemente "no".

JJ Moyer: Circuito de conmutación de verificación de paridad, patente de los Estados Unidos US3011073, 1961

AF Bulver et al .: realización de la compuerta NAND de la función de paridad de entrada n, patente de los Estados Unidos US3718904, 1973

PJ Baun, Jr .: Parity Circuits, patente de los Estados Unidos US4251884, 1981

Johne, ¿cuál es tu problema? Estás tratando de discutir sobre cosas que nadie afirmó. Nadie dijo que el límite inferior de paridad plantea algún límite fundamental para calcular XOR con circuitos distintos de aquellos para los que se aplica el teorema (es decir, circuitos AC ^ 0). No hay suposiciones ocultas o implicaciones veladas aquí. En particular, todos sabemos, por ejemplo, que es posible calcular XOR con circuitos NAND de tamaño logarítmico de tamaño polinómico, incluso con un fan-in constante.

La cita de Shannon también es en gran medida irrelevante. No hay indicios de que sospeche que los circuitos AND-OR de profundidad constante deben tener un tamaño exponencial para calcular la paridad. Por supuesto, podría haberlo adivinado, ya que es fácil conjeturar que esto debería ser cierto después de jugar con el problema por un tiempo, pero ¿y qué?

Te estás perdiendo por completo el punto: probar límites más bajos es extremadamente difícil, y tenemos que comenzar en alguna parte, con los modelos más simples. Este fue esencialmente el primer límite inferior del circuito, las técnicas conducen a muchas ideas interesantes (incluidos otros campos como la teoría del aprendizaje), y aunque el resultado es plausible, la prueba es perspicaz y nada trivial.

El hecho de que el resultado parezca intuitivo no lo hace obvio; Si cree que es así, proporcione una prueba de que la paridad no está en AC ^ 0. Todos saben que P no es igual a NP también para el caso, pero nadie está cerca de tener una prueba.

Sus quejas en otros hilos sobre las puertas NAND tampoco tienen sentido. Este límite inferior se mantiene igualmente bien para circuitos de profundidad constante construidos a partir de puertas NAND, ya que son básicamente lo mismo. Elegir indicar el resultado con AND, OR, NOT es solo una cuestión de conveniencia. Por lo tanto, esta puede ser una aplicación del mundo real en términos que le gusten: los circuitos de profundidad constante de paridad de cálculo de puertas NAND requieren un tamaño exponencial. Da una limitación práctica, incluso si eso no es lo más importante. Dice que los pequeños circuitos XOR para un gran número n de entradas deben tener una profundidad creciente con n o puertas que no sean NAND. ¿Por qué no estás satisfecho con esto?

Su afirmación de que la profundidad del circuito no es un problema en el mundo real también es muy engañosa, ya que la profundidad está directamente relacionada con el tiempo y la frecuencia máxima a la que puede operar el reloj.

Por cierto, la comunidad CS conocía bien la teoría del circuito booleano EE y se basó en eso, al contrario de lo que usted afirma.

$1.62^2$$3.82^2$

• Estructuras de circuito lógico de tecnología CMOS

$s = a \oplus b \oplus c_{in}$

• Celda sumadora completa 8T de alta velocidad y baja potencia

Un buen lugar para encontrar puertas XOR / XNOR compactas de alta velocidad es en los sumadores completos y los circuitos Hamming ECC (que generalmente están en la ruta crítica).

Además, el problema de la profundidad del circuito no suele ser un problema en la lógica síncrona VLSI. La única profundidad de cualquier consecuencia es la ruta crítica, que define el período de reloj máximo. La gran mayoría de la lógica combinatoria propaga sus resultados en una fracción del tiempo para la ruta crítica. Las rutas críticas tienden a ocurrir con cierta lógica combinatoria que necesita pasar por varias áreas dispersas en un chip.

$n$$O(1)$

$AT^2 = \Omega(n^2)$

• Sobre la complejidad de las implementaciones de VLSI y las representaciones gráficas de funciones booleanas con aplicación a la multiplicación de enteros

Esto es del Blog de Complejidad de Computación:

Esto plantea la pregunta: ¿algunas personas en el mundo real real realmente quieren construir circuitos de fan-and-or-NOT fanin ilimitados de profundidad constante sin límites para PARITY, y este resultado les dice por qué no pueden?

$2^n/n$

$\lambda(3) = 8$

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

$\mu(3)$

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

$4(n-1)$