Изменения
Нет описания правки
{{Лемма
|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=
}}
{{Теорема
|statement=
