О сложности реализации симметрических функций формулами

Доказывается, что всякую симметрическую функцию $k$-значной логики от $n$ аргументов можно в любом базисе реализовать формулой, сложность которой не превосходит по порядку $n^C$, где $C$ — константа, зависящая от базиса. Показано, что в случае $k=2$ для всех базисов $C\leqslant 4,93$. Библ. 7 назв.