О реализации линейной функции формулами в различных базисах

Исследуется сложность реализации линейной булевой функции $x_1\otimes x_2\otimes\dots\otimes x_n$ формулами в различных базисах. Все базисы удалось разбить на три типа; в базисах первого типа сложность линейной функции по порядку равна $n^2$: в базисах второго – по порядку не меньше, чем $n^\beta$, и не больше, чем $n^\gamma$, где $1<\beta<\gamma<2$ (константы $\beta$ и $\gamma$ вычисляются по базису); в базисах третьего типа по порядку равна $n$.
Библиогр. 8.