100
правок
Изменения
→Теорема
<tex>\oplus \notin \mathrm{AC^0}</tex>.
|proof=
Рассмотрим произвольную схему из [[Классы 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>\mathrm{AC^0}</tex> в виде КНФ или ДНФ. Не умаляя общности, будем считать, что:
[[Файл:afterHastadSwitchingTransformation.png|600x250px|thumb|center|Схема после применения леммы.]]
Заметим, что лемма применяется не более, чем к <tex>n_0^b</tex> элементам исходной схемы. Тогда с вероятностью не менее <tex>1 - \frac{n_0^b}{10n_0^b} = \frac{9}{10}</tex> после (<tex>d-2</tex>)-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных.
}}
