Reducción de profundidad para circuitos booleanos

Este resultado de Tavenas, Koiran y otros muestran que cualquier polinomio calculado por un circuito de tamaño $s$ se calcula por un circuito homogéneo de profundidad 4 de tamaño $s^{\sqrt{d}}$ .

¿Hay resultados similares para los circuitos booleanos o sabemos por qué tal cosa no es posible?

cc.complexity-theory circuit-complexity arithmetic-circuits Estudiante de matemáticas
fuente

Si recuerdo correctamente, ese resultado no es posible en el mundo booleano. Tengo problemas para recordar el resultado específico, creo que tal vez esto es arxiv.org/abs/1504.03398 puntos hacia esta dirección. Puedo actualizar esto a una respuesta si encuentro la referencia real que recuerdo vagamente.

chazisop

Respuestas:

Desafortunadamente, las reducciones de profundidad más conocidas para circuitos booleanos solo funcionan para clases de circuitos muy restringidas. Valiant ( Valiant ; Viola ) demostró que un circuito de tamaño $O(n)$ y profundidad $O(\log{n})$ puede calcularse mediante un circuito de profundidad 3 de tamaño $2^{O(n/\log\log{n})}$ . Además, Valiant mostró una reducción de profundidad similar para circuitos en serie-paralelo de tamaño lineal (una subclase natural de circuitos), ver Calabro .

Tenga en cuenta que el número de puertas en un circuito de profundidad 3 que calcula una función aleatoria es $\Theta(2^{n/2})$ ( Dančík ; Sergeev ), mientras que el mejor límite inferior que podemos probar es solo $2^{\Omega(\sqrt{n})}$ (Håstad;Håstad, Jukna, Pudlák;Paturi, Pudlák, Zane;Boppana;Paturi, Pudlák, Saks, Zane;Meir, Wigderson).

Alex Golovnev
fuente

Vale la pena incluirlo como comentario: también hay resultados de reducción de profundidad para

(otra clase muy restringida). Profundidad-

circuitos con AND, OR, NOT o MOD m se puede convertir en profundidad-

circuitos de la forma SYM-Y de manera que el tamaño es

y la puerta inferior fan-in is

(a través de Yao, Beigel-Tarui, Chen-Papakonstantinou)

{A C C}^{0}

$\mathsf{ACC}^0$

d

$d$

2

$2$

2^{p o l y l o g (n)}

$2^{polylog(n)}$

p o l y l o g (n)

$polylog(n)$

Sam McGuire