Аннотация:Показано, что сложность реализации функции подсчета числа единиц в булевом наборе длины n формулами над базисом двуместных булевых функций не превосходит O(n^3,06), а над стандартным базисом O(n^4,54). Как следствие, такие же оценки справедливы длясложности любой пороговой симметрической функции n переменных, в частности, для функции голосования. Попутно получены оценки сложности произвольных симметрических функций n переменных: O(n^3,23) и O(n^4,82) над теми же базисами.
