УДК 519.6
О нижних оценках сложности схем в базисе антицепных функций / О. В. Подольская. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2013. № 2. С. 17-23.
Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка √n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных.
Ключевые слова: антицепная функция, булевы схемы, линейная функция, функция голосования.
Библиогр. 5.
