Изменения
Нет описания правки
{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде k-ДНФ, а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно , что <tex>Pr[f|_p</tex> не представима в виде s-КНФ<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>.
|proof=
}}
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из <tex>\mathrm{AC^0}</tex>. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет <tex>2n</tex> входных провода, причем последние <tex>n</tex> из них являются отрицанием первых <tex>n</tex> входов.
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
# Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью на <tex>1</tex> уменьшить глубину схемы, сохранив при этом число входов. Пусть <tex>n~-</tex> длина входной цепочки. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n^b</tex> было не меньше, чем число элементов в схеме. На каждом шаге случайным образом будем назначать все большее число переменных. Обозначим <tex>n_i~-</tex> число неназначенных переменных на <tex>i</tex>-ом шаге. Тогда на <tex>i + 1</tex>-ом шаге число назначенных переменных будет <tex>n_i - \sqrt{n_i}</tex>. Возьмем <tex>k_i=10b2^i.</tex>
}}
