Сложность реализации симметрических булевых функций схемами в базисе антицепных функций

Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе, состоящем из всех характеристических функций антицепей на булевом кубе. Установлено точное значение сложности реализации произвольной симметрической функции схемами в этом базисе. В частности, для функций четности и голосования от $n$ переменных при всех натуральных $n\geq1$ получены точные значения сложности: $\lfloor \frac{n+1}{2} \rfloor$ и $\left\lfloor \frac{n}{2} \right \rfloor +1$ соответственно. Установлено, что наибольшая сложность булевых функций от $n$ переменных при реализации схемами в этом базисе по порядку роста равна $n$. Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 14–01–00598.