УДК 519.6

О нижних оценках сложности схем в базисе антицепных функций / О. В. Подольская. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. ? 2. С. 17-23.

Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка √n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных.

Ключевые слова: антицепная функция, булевы схемы, линейная функция, функция голосования.

Библиогр. 5.