Изменения

Допустим, что схема из [[Классы NC и AC| класса]] <tex>\mathrm{AC^0}</tex> распознает язык <tex>\oplus</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>.