Перцептроны с большим весом

Пороговым элементом называется линейная комбинация входных переменных с целыми коэффициентами (весами). Он выдает 1, если сумма положительна. Максимальное абсолютное значение коэффициентов порогового элемента называется его весом. Перцептрон степени $d$ – это булева схема глубины 2 с пороговым элементом в вершине и произвольными булевыми элементами входной степени не выше $d$ на нижнем уровне. Весом перцептрона называется вес его порогового элемента.
Для всякого постоянного $d\geq 2$, не зависящего от числа входных переменных $n$, мы строим перцептрон степени $d$, для которого требуются веса, не меньшие $n^{\Omega(n^d)}$, т.е. вес всякого перцептрона степени $d$, вычисляющего ту же булеву функцию, должен быть не меньше $n^{\Omega(n^d)}$. Эта оценка точна: всякий перцептрон степени $d$ эквивалентен перцептрону степени $d$ с весом $n^{O(n^d)}$ Для случая пороговых элементов (т.е. $d=1$) результат был доказан Хостадом в [2]; мы используем технику Хостада.