?
Об оценках функций Шеннона сложности схем в некоторых бесконечных базисах
В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности булевых функций от n переменных. Второй базис состоит из функций голосования и антицепных функций от любого числа переменных. Доказано, что в этом базисе наибольшая сложность булевых функций от n переменных по порядку роста равна logn.