Изменения

<tex>\oplus \notin \mathrm{AC^0}</tex>.

|proof=

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

поэтому ни одна схема из этого класса не может распознавать язык <tex>\oplus</tex>.

Покажем, как представить схему из класса <tex>\mathrm{AC^0}</tex> в виде <tex>k</tex>-КНФ или <tex>k</tex>-ДНФ. Не умаляя общности, будем считать, что:

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