На обманывают

У меня есть несколько вопросов, касающихся обмана контуров постоянной глубины.

1. Известно, что независимость необходима для обмана A C 0 цепей глубины d , где n - размер входа. Как это можно доказать?$\log^{O(d)}(n)$$AC^0$$d$$n$
2. Поскольку вышеприведенное верно, любой псевдослучайный генератор, который обманывает схемы глубины d, должен обязательно иметь начальную длину l = Ω ( log d ( n ) ) , что будет означать, что нельзя ожидать, что R A C 0 = A C 0 через PRG. Я верю R A C 0 ? = A C 0 все еще остается открытым вопросом, так что это означает, что для доказательства R A C необходимо использовать методы, отличные от PRG$AC^0$$d$$l = \Omega(\log^d(n))$$RAC^0 = AC^0$$RAC^0 \stackrel{?}{=} AC^0$ . Я нахожу это странным, потому что, по крайней мере, в случае P ? = B P P , мы считаем, что PRG - это, по сути,единственныйспособ ответить на этот вопрос.$RAC^0 = AC^0$$P \stackrel{?}{=} BPP$

Я думаю, что мне не хватает чего-то действительно базового здесь.

1) Что подразумевается под необходимостью, так это то, что один из способов создания независимого от распределения - это разбить входные данные на блоки по k + 1 бит, и пусть ( k + 1 ) -й бит каждого блока будет равенством другие k бит в блоке. Очевидно, что это распределение может быть нарушено только путем вычисления четности на k битах. Заявленный вами результат следует из того факта, что поли ( n ) схемы глубины d могут вычислить четность по логарифму d - 1 n бит.$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}$