Изменения

Пусть функция <tex>f</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайная выборка случайное назначение <tex>t</tex> случайных бит входаслучайно выбранным аргументам случайно выбранных значений. Тогда при <tex>s \ge 2</tex> верно, что : <br><tex>PrP[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}.</tex>

Заметим, что для '''Замечание.''' Для функции <tex>\overline{f}</tex> можно получить такой же результат, изменив КНФ на ДНФ и наоборот.