Oszukiwanie

Mam kilka pytań dotyczących oszukiwania obwodów o stałej głębokości.

1. Wiadomo, że -wise niezależności konieczne oszukać A C 0 obwody głębokości D , gdzie n jest wielkości wejściowych. Jak można to udowodnić?$\log^{O(d)}(n)$$AC^0$$d$$n$
2. Ponieważ powyższe jest prawdziwe, każdy generator pseudolosowy, który głupcy C 0 obwody głębokości D musi koniecznie mieć długość nasion l = omów ( log d ( n ) ) , co oznaczałoby, że nie można oczekiwać, aby udowodnić, R C 0 = C 0 przez PRG. Wierzę, że R A C 0 ? = A C 0 jest wciąż pytaniem otwartym, więc oznacza to, że trzeba użyć technik innych niż PRG, aby udowodnić R A C$AC^0$$d$$l = \Omega(\log^d(n))$$RAC^0 = AC^0$$RAC^0 \stackrel{?}{=} AC^0$ . Uważam to za dziwne, ponieważ przynajmniej w przypadku P ? = B P P , uważamy, że PRG są zasadniczojedynądrogą do odpowiedzi na to pytanie.$RAC^0 = AC^0$$P \stackrel{?}{=} BPP$

Myślę, że brakuje mi czegoś naprawdę podstawowego.

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