Lema de conmutación

En la teoría de la complejidad computacional , el lema de conmutación de Håstad es una herramienta clave para demostrar límites inferiores en el tamaño de circuitos booleanos de profundidad constante . Fue introducido por primera vez por Johan Håstad para demostrar que los circuitos booleanos AC 0 de profundidad k requieren tamaño para calcular la función de paridad en bits. ^[1] Más tarde recibió el Premio Gödel por este trabajo en 1994. ${\displaystyle \exp(\Omega (n^{1/(k-1)}))}$ ${\displaystyle n}$

El lema de conmutación describe el comportamiento de un circuito de profundidad 2 bajo restricción aleatoria , es decir, cuando se fijan aleatoriamente la mayoría de las coordenadas en 0 o 1. Específicamente, del lema se deduce que una fórmula en forma normal conjuntiva (es decir, un AND de OR) se convierte en una fórmula en forma normal disyuntiva (un OR de AND) bajo restricción aleatoria, y viceversa. Este "cambio" le da al lema su nombre.

Declaración

Considere una fórmula de ancho en forma normal disyuntiva , el OR de cláusulas que son el AND de literales w ( o su negación ). Por ejemplo, es un ejemplo de una fórmula en esta forma con ancho 2. ${\displaystyle w}$ ${\displaystyle F=C_{1}\vee C_{2}\vee \cdots \vee C_{m}}$ ${\displaystyle C_{\ell }}$ ${\displaystyle x_{i}}$ ${\displaystyle \neg x_{i}}$ ${\displaystyle (\neg x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})\vee (x_{2}\wedge x_{3})}$

Sea la fórmula bajo una restricción aleatoria: cada uno se establece independientemente en 0 o 1 con probabilidad . Entonces, para una constante C suficientemente grande , el lema de conmutación establece que ${\displaystyle F|R_{p}}$ ${\displaystyle x_{i}}$ ${\displaystyle (1-p)/2}$

${\displaystyle \Pr[\operatorname {DT} (F\mid R_{p})\geq t]<C(pw)^{t},}$

donde denota la complejidad del árbol de decisión , la cantidad de bits necesarios para calcular la función . ^[2] ${\displaystyle \operatorname {DT} (f)}$ ${\displaystyle x}$ ${\displaystyle f}$

Prueba

Intuitivamente, el lema de conmutación es válido porque las fórmulas DNF se reducen significativamente bajo restricciones aleatorias: cuando un literal en una cláusula se establece en 0, toda la cláusula AND se evalúa como cero y, por lo tanto, puede descartarse.

La prueba original del lema de conmutación (Håstad 1987) implica un argumento con probabilidades condicionales . Se podría decir que Razborov (1993) y Beame (1994) han presentado posteriormente pruebas posiblemente más sencillas. Para una introducción, véase el capítulo 14 en Arora & Barak (2009).

Límites en AC0circuitos

El lema de conmutación es una herramienta clave utilizada para comprender la clase de complejidad de circuitos AC 0 , que consiste en circuitos de profundidad constante que consisten en AND, OR y NOT. La aplicación inicial de Håstad de este lema fue establecer límites inferiores exponenciales estrictos para dichos circuitos que calculan PARITY , mejorando los límites inferiores superpolinómicos anteriores de Merrick Furst, James Saxe y Michael Sipser ^[3] e independientemente Miklós Ajtai . ^[4] Esto se hace aplicando el lema de conmutación veces, donde es la profundidad del circuito: cada aplicación elimina una capa del circuito hasta que se queda con un circuito muy simple, mientras que PARITY sigue siendo PARITY bajo restricción aleatoria, y por lo tanto sigue siendo complejo. Por lo tanto, un circuito que calcula PARITY debe tener una gran profundidad. ^[5] ${\displaystyle d-1}$ ${\displaystyle d}$

El lema de conmutación es la base de los límites del espectro de Fourier de los circuitos de CA ^{0 [5]} y de los algoritmos para aprender dichos circuitos. ^[6]

Véase también

• CA 0
• Circuito booleano
• Satisfacibilidad del circuito
• Problema de valor del circuito
• Función de paridad

Referencias

1. Håstad, Johan (1986). "Límites inferiores casi óptimos para circuitos de poca profundidad". Actas del decimoctavo simposio anual de la ACM sobre teoría de la computación - STOC '86 . ACM Press. págs. 6–20. doi :10.1145/12130.12132. ISBN 978-0-89791-193-1.
2. Rossman, Benjamín (2019). "Criticidad de las fórmulas regulares". Miguel Wagner. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 28 páginas. doi : 10.4230/LIPICS.CCC.2019.1 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
3. Merrick Furst, James Saxe y Michael Sipser, "Paridad, circuitos y la jerarquía de tiempo polinomial", Annu. Intl. Symp. Found. Computer Sci., 1981, Theory of Computing Systems , vol. 17, n.º 1, 1984, págs. 13-27, doi :10.1007/BF01744431
4. Miklós Ajtai, " -Fórmulas sobre estructuras finitas", Anales de lógica pura y aplicada , 24 (1983) 1–48. ${\displaystyle \Sigma _{1}^{1}}$
5. Tal, Avishay (2017). "Límites estrechos en el espectro de Fourier de AC0". Marc Herbstritt. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 31 páginas. doi : 10.4230/LIPICS.CCC.2017.15 . {{cite journal}}: Requiere citar revista |journal=( ayuda )
6. Linial, Nathan; Mansour, Yishay; Nisan, Noam (1 de julio de 1993). "Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje". Revista de la ACM . 40 (3): 607–620. doi : 10.1145/174130.174138 . ISSN  0004-5411.

• Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno, Cambridge , ISBN 978-0-521-42426-4, Zbl1193.68112 ​
• Beame, Paul (1994), "Una introducción al lema de conmutación", manuscrito
• Håstad, Johan (1987), Limitaciones computacionales de circuitos de pequeña profundidad (PDF) , tesis doctoral, Instituto Tecnológico de Massachusetts.
• Razborov, Alexander A. (1993), "Una equivalencia entre la aritmética acotada de dominio de segundo orden y la aritmética acotada de primer orden", Aritmética, teoría de la prueba y complejidad computacional , 23 : 247–277, doi : 10.1093/oso/9780198536901.003.0012, ISBN 978-0-19-853690-1