En engañar

Tengo algunas preguntas sobre engañar a los circuitos de profundidad constante.

1. Se sabe que la independencia de es necesaria para engañar a los circuitos A C 0 de profundidad d , donde n es el tamaño de la entrada. ¿Cómo se puede probar esto?$\log^{O(d)}(n)$$AC^0$$d$$n$
2. Como lo anterior es cierto, cualquier generador pseudoaleatorio que engañe a los circuitos de profundidad d necesariamente debe tener una longitud de semilla l = Ω ( log d ( n ) ) , lo que significa que no se puede esperar probar R A C 0 = A C 0 a través de PRG. Creo que R A C 0 ? = A C 0 sigue siendo una pregunta abierta, por lo que esto significa que uno tiene que usar otras técnicas que no sean PRG para probar R A $AC^0$$d$$l = \Omega(\log^d(n))$$RAC^0 = AC^0$$RAC^0 \stackrel{?}{=} AC^0$ . Esto me parece extraño porque, al menos en el caso de P ? = B P P , creemos que los PRG son esencialmente laúnicaforma de responder esta pregunta.$RAC^0 = AC^0$$P \stackrel{?}{=} BPP$

Creo que me estoy perdiendo algo realmente básico aquí.

$k$$k+1$$(k+1)$$k$$k$$n$$d$$\log^{d-1} n$

$k$$O(\log n)$

$AC^{0}$$(n-1)$$(n-1)$$n$$\epsilon$

$\log^{O(d)} n$$AC^{0}$