О НИЖНИХ ОЦЕНКАХ СЛОЖНОСТИ СХЕМ В БАЗИСЕ АНТИЦЕПНЫХ ФУНКЦИЙ

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

• Подольская О.В.

• Прикладные науки. Медицина. Технология

• Естественные науки