Небольшое уменьшение степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину

Булева функция $f\colon\{-1,+1\}^n\to\{-1,+1\}$ называется знаковой функцией целочисленного многочлена $p(x)$, если $f(x)=\operatorname{sgn}(p(x))$ для всех $x\in\{-1,+1\}^n$. При этом многочлен $p(x)$ называется пороговым элементом для булевой функции $f$. Весом порогового элемента называется сумма абсолютных значений коэффициентов $p$. Доказывается, что небольшое изменение степени порогового элемента для заданной функции может сильно сказаться на величине необходимого веса. Более точно, для всякого $d=1,2,\dots,n-1$ явно строится функция $f\colon\{-1,+1\}^n\to\{-1,+1\}$, требующая веса $\exp\{\Theta(n)\}$ при представлении пороговыми элементами степени $d$ и представимая пороговым элементом степени $d+1$ с весом лишь $O(n^2)$. Нижняя оценка $\exp\{\Theta(n)\}$ для степени $d$ остается верной и для размера булевой схемы глубины 2 с функцией голосования на верхнем уровне и произвольными элементами входной степени $d$ на нижнем уровне. Этот разрыв в величине весов экспоненциально больше, чем известные ранее. Аналогичный результат доказывается для длины порогового элемента, т.е. числа одночленов в нем.
Библиография: 35 названий.