Построение универсальных нумераторов и формул для пороговых функций

Рассматривается булевская функция $Th_T(x_0,\dots,x_{N-1})$, равная единице, когда по крайней мере $T$ ее переменных равны единице. Для нее строится формула в базисе $\bigvee$, $\bigwedge$, имеющая $N\log N e^{T(1+o(1))}$ вхождений переменных, за время $N(\log N)^3e^{T(1+o(1))}$. Наилучший из ранее известных результатов принадлежал Фридману, который для постоянного $T$ и $N\to\infty$ находил формулу, имеющую $O(N\log N)$ вхождений переменных за полиномиальное по $N$ время. Для этого случая наш метод дает формулу той же сложности, но за почти линейное время. Наш результат близок к окончательному в том смысле, что почти минимальная среди формул глубины $3$ формула строится за почти минимальное время.
Табл. 3, библиогр. 15.