100
правок
Изменения
Нет описания правки
===Hastad’s switching lemma===
{{Лемма
|statement=
Пусть <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайная выборка <tex>t</tex> случайных бит входа. Тогда при <tex>s \ge 2</tex> верно, что <tex>Pr[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>
|proof=
}}
Заметим, что для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.
===Теорема===
{{Определение
