Pada menipu

Saya punya beberapa pertanyaan tentang menipu sirkuit kedalaman konstan.

1. Ini diketahui bahwa kemerdekaan-bijaksana adalah diperlukan untuk menipu A C 0 sirkuit kedalaman d , di mana n adalah ukuran input. Bagaimana seseorang bisa membuktikan ini?$\log^{O(d)}(n)$$AC^0$$d$$n$
2. Karena di atas adalah benar, setiap pseudorandom generator yang bodoh sirkuit kedalaman d tentu harus memiliki panjang benih l = Ω ( log d ( n ) ) , yang kemudian akan berarti bahwa seseorang tidak dapat berharap untuk membuktikan R A C 0 = A C 0 melalui PRG. Saya percaya R A C 0 ? = A C 0 masih merupakan pertanyaan terbuka, jadi ini berarti seseorang harus menggunakan teknik selain PRG untuk membuktikan R A $AC^0$$d$$l = \Omega(\log^d(n))$$RAC^0 = AC^0$$RAC^0 \stackrel{?}{=} AC^0$ . Saya menemukan ini aneh karena, setidaknya dalam kasus P ? = B P P , kami percaya bahwa PRG pada dasarnya adalahsatu-satunyacara untuk menjawab pertanyaan ini.$RAC^0 = AC^0$$P \stackrel{?}{=} BPP$

Saya pikir saya kehilangan sesuatu yang sangat mendasar di sini.

$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}$