Изменения

Рассмотрим произвольную схему из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex>. Допустим, что эта схема распознает язык <tex>\oplus</tex>. В силу особенности языка <tex>\oplus</tex>, распознающая его схема должна зависить от значений всех своих входов. Однако воспользовавшись леммой, можно с вероятностью, отличной от нуля, представить эту схему в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ. Заметим, что значение <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ можно сделать постоянным, зафиксировав значение не более, чем <tex>k</tex> входов. Для этого надо зафиксировать значение лишь одного дизъюнкта или конъюнкта соответственно. Поскольку вероятность представить произвольную схему из класса <tex>\mathrm{AC^0}</tex> в таком виде отлична от нуля, то можно подобрать значения для части входов так, чтобы значение схемы не зависело от оставшихся. А значит, ни одна схема из класса <tex>\mathrm{AC^0}</tex> не распознает язык <tex>\oplus</tex>, поскольку зависит не от всех входных значений.

# Выходная степень каждого элемента равна <tex>1</tex>.

# Схема не содержит элементов <tex>\neg</tex>. В самом деле, вместо схемы с элементами <tex>\neg</tex> можно рассмотреть эквивалентную ей схему из класса <tex>\mathrm{AC^0}</tex> с удвоенным числом входов, причем значения, подаваемые на добавленные входы будут противоположны значениям, подаваемым на исходные входы схемы.

[[Файл:beforeHastadSwitchingTransformation.png|600x250px|thumb|center|Схема на <tex>i</tex>-ом шаге.]]

* База индукции верна. Глубина исходной схемы равна <tex>d</tex>, а входная степень каждого элемента равна <tex>1</tex>, что меньше <tex>k_0 = 10b.</tex>

* Индукционный переход. Допустим, что после <tex>i</tex>-ого шага глубина схемы будет <tex>d - i</tex>, причем наибольшая степень входа элемента на нижнем уровне не будет превосходить <tex>k_i</tex>. Если нижний уровень схемы состоит из <tex>\land</tex> элементов, тогда уровень выше <tex>-</tex> из элементов <tex>\lor</tex>. Каждый <tex>\lor</tex> элемент можно считать <tex>k_i</tex>-ДНФ. Воспользуемся леммой. Пусть <tex>s = k_{i+1}</tex>, <tex>n~-</tex> число входов схемы, соответствующих рассматриваемому элементу <tex>\lor</tex>. Тогда в качестве <tex>t</tex> возьмем <tex>n - \frac{n}{\sqrt{n_i}}</tex>. Значит, с вероятностью не менее <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2}</tex> функцию нельзя представить в виде <tex>k_{i+1}</tex>-КНФ. Поскольку <tex>t</tex> выбиралось таким образом, то при переходе к следующему шагу число входов схемы уменьшилось в <tex>\sqrt{n_i}</tex> раз, поэтому <tex>n_i = n_0^{1/2^i}.</tex> Тогда при достаточно больших <tex>n_0</tex> верно, что <tex>\left(\frac{k_i^{10}}{\sqrt{n_i}}\right) ^ {k_{i+1}/2} = \left(\frac{k_i^{10}}{n_0^{1/2^{i+1}}}\right) ^ {k_{i+1}/2} \le \frac{1}{10n_0^b}</tex>. В итоге получаем, что <tex>k_i</tex>-ДНФ можно переписать в виде <tex>k_{i+1}</tex>-КНФ с вероятностью не менее <tex>1 - \frac{1}{10n_0^b}</tex>. Поскольку верхний уровень КНФ состоит из <tex>\land</tex> элементов, также как и уровень над КНФ, то их можно объединить, уменьшив при этом глубину схемы на <tex>1</tex>. Аналогично рассматриваем случай, когда нижний уровень схемы состоит из <tex>\lor</tex> элементов.

[[Файл:afterHastadSwitchingTransformation.png|600x250px|thumb|center|Схема после применения леммы.]]

}}