Redução de profundidade para circuitos booleanos

Este resultado de Tavenas, Koiran e outros mostra que qualquer polinômio calculado por um circuito de tamanho $s$ é calculado por um circuito homogêneo de profundidade 4 do tamanho $s^{\sqrt{d}}$ .

Existem resultados semelhantes para circuitos booleanos ou sabemos por que isso não é possível?

cc.complexity-theory circuit-complexity arithmetic-circuits Aprendiz de matemática
fonte

Se bem me lembro, esse resultado não é possível no mundo booleano. Estou tendo problemas para lembrar o resultado específico, acho que talvez seja isso arxiv.org/abs/1504.03398 aponta nessa direção. Posso atualizar isso para uma resposta se encontrar a referência real de que me lembro vagamente.

chazisop 28/02/19

Respostas:

$O(n)$ $O(\log{n})$ $2^{O(n/\log\log{n})}$

$\Theta(2^{n/2})$ $2^{\Omega(\sqrt{n})}$

Alex Golovnev
fonte

{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)$