Изменения

Рассмотрим произвольную схему из [[Классы 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>, поскольку зависит не от всех входных значений.