Изменения
Нет описания правки
===Hastad’s switching lemma===
{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде k-ДНФ, а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде s-КНФ<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>.
|proof=
}}
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
===Теорема===
{{Теорема
|statement=
Заметим, что лемма применяется не более, чем к <tex>n^b</tex> элементам исходной схемы. Тогда с вероятностью <tex>9/10</tex> после <tex>d-2</tex>-ого шага получаем схему глубины <tex>2</tex>, у которой максимальная степень входа на нижнем уровне не больше <tex>k_{d-2}</tex>. По построению эта формула либо КНФ, либо ДНФ. Такую схему можно сделать постоянной, если правильно зафиксировать <tex>k_{d-2}</tex> переменных. Однако функцию <tex>\oplus</tex> невозможно сделать постоянной, зафиксировав менее <tex>n</tex> переменных. Получили противоречие. Поскольку рассматривали произвольную схему из класса <tex>\mathrm{AC^0}</tex>, верно что <tex>\oplus \notin \mathrm{AC^0}.</tex>
}}
===Источники===
* ''Sanjeev Arora, Boaz Barak''. [http://www.cs.princeton.edu/theory/complexity Computational Complexity: A Modern Approach]
