Изменения
→Теорема
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>. Допустим, что эта схема распознает язык <tex>\oplus</tex>. В силу особенности языка <tex>\oplus</tex> распознающая его схема должна зависить от всех своих входов. Однако воспользовавшись леммой, можно с большой вероятностью представить эту схему в виде КНФ или ДНФ. Заметим, что значение КНФ или ДНФ можно сделать постоянным, зафиксировав значение лишь одного дизъюнкта или конъюнкта соответственно. А значит, с высокой вероятностью произвольная схема из класса <tex>\mathrm{AC^0}</tex> не распознает язык <tex>\oplus</tex>, поскольку зависит не от всех входных значений. Покажем, как представить схему из класса <tex>\mathrm{AC^0}</tex> в виде КНФ или ДНФ. Не умаляя общности, будем считать, что:
# Выходная степень каждого элемента равна <tex>1</tex>.
# Схема имеет не содержит элементов <tex>2n_0\neg</tex> входных провода. Вместо этого удвоим число входов, причем последние <tex>n_0</tex> из них являются отрицанием первых <tex>n_0</tex> входовзначения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы.
# Элементы <tex>\lor</tex> и <tex>\land</tex> чередуются. Значит, схему можно разбить на уровни так, что на каждом уровне все элементы будут одинаковыми.
# Все входы лежат на одном уровне. Нижний уровень схемы состоит из <tex>\land</tex> элементов с единичной степенью входа.
Построим итеративный процесс, на каждом шаге которого можно с высокой вероятностью уменьшить глубину схемы на <tex>1</tex>, сохранив при этом число входов. Пусть <tex>d~-</tex> глубина схемы, а <tex>n_0~-</tex> число входов. Выберем минимальное целое <tex>b</tex> так, чтобы <tex>n_0^b</tex> было не меньше, чем число элементов в схеме. Обозначим <tex>n_i~-</tex> число входов схемы после <tex>i</tex>-го шага. Возьмем <tex>k_i=10b\cdot2^i.</tex>
[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]
