Формульная сложность линейной функции в $k$-арном базисе

В работе предлагается способ расширения метода Храпченко нижней оценки сложности бинарных формул на формулы в $k$-арных базисах. Полученное расширение позволяет сложность линейной булевой функции и функции голосования $n$ переменных при реализации формулами в базисе из всех $k$-местных монотонных функций и отрицания оценить как $\Omega(n^{g(k)})$, где $g(k)=1+\Theta(1/\ln k)$. Для линейной функции оценка сложности в таком виде неулучшаема. При $k=3$ доказывается более аккуратная нижняя оценка $\Omega(n^{1.53})$.
Библиография: 18 названий.