Изменения

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