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 los circuitos booleanos de profundidad constante . Utilizando el lema de conmutación, Johan Håstad ( 1987 ) mostró que los circuitos booleanos de profundidad k en los que solo se permiten puertas lógicas Y, O y NO requieren tamaño
para calcular la función de paridad .
El lema de conmutación dice que los circuitos de profundidad 2 en los que alguna fracción de las variables se han establecido aleatoriamente dependen con alta probabilidad solo de muy pocas variables después de la restricción. El nombre del lema de conmutación se deriva de la siguiente observación: Tome una fórmula arbitraria en forma normal conjuntiva , que es en particular un circuito de profundidad 2. Ahora, el lema de conmutación garantiza que después de establecer algunas variables al azar, terminamos con una función booleana que depende solo de unas pocas variables, es decir, puede ser calculada por un árbol de decisión de cierta profundidad.. Esto nos permite escribir la función restringida como una fórmula pequeña en forma normal disyuntiva . Por lo tanto, una fórmula en forma normal conjuntiva afectada por una restricción aleatoria de las variables puede "cambiarse" a una fórmula pequeña en forma normal disyuntiva.
La prueba original del lema de cambio ( Håstad 1987 ) implica un argumento con probabilidades condicionales . Razborov (1993) y Beame (1994) han dado posteriormente pruebas posiblemente más simples . Para una introducción, consulte el Capítulo 14 en Arora & Barak (2009) .
Referencias
- Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , ISBN 978-0-521-42426-4, Zbl 1193.68112
- Beame, Paul (1994), "A Switching Lemma Primer", Manuscrito
- Håstad, Johan (1987), Limitaciones computacionales de circuitos de pequeña profundidad (PDF) , Ph.D. tesis, Instituto de Tecnología de Massachusetts.
- Razborov, Alexander A. (1993), "Una equivalencia entre aritmética acotada de dominio acotado de segundo orden y aritmética acotada de primer orden", Aritmética, teoría de la prueba y complejidad computacional , 23 : 247–277