О сложности дизъюнктивной нормальной формы пороговых функций

В работе рассматривается задача оценки сложности дизъюнктивной нормальной формы (д. н. ф.), понимаемой как минимальное число простых импликант, входящих в запись д. н. ф. пороговых функций от $n$ переменных. До этого было известно, что у почти всех пороговых функций сложность д. н. ф. не меньше $n^2/\log_2n$. В работе доказаны неравенства, связывающие сложность д. н. ф. $L\nu(f)$ пороговой функции $f$ с параметрами Чоу. С их помощью показано, что при достаточно больших $n$ для почти всех пороговых функций
$$ \log_2 L\nu(f)>n-2\sqrt{2n\log_2 n}(1+\delta(n)), $$
где $\delta(n)$ — любая функция такая, что $\delta(n)\to0$ и $n\delta(n)\to\infty$ при $n\to\infty$.