Изменения

Заметим, что лемма применяется не более, чем к <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> переменных. Однако функцию, распознающую <tex>\oplus,</tex> невозможно сделать постоянной, зафиксировав не все переменные. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrm{AC^0}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}.</tex>