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

Изучается сложность реализации булевых функций схемами из функциональных элементов в бесконечном базисе $AC$, состоящем из всевозможных антицепных булевых функций. Показано, что при $n\to\infty$ порядок роста сложности реализации линейной функции $n$ переменных схемами в базисе $AC$ не меньше $(n/\ln n)$. Установлено, что наибольшая сложность булевых функций $n$ переменных при реализации схемами в базисе $CA$ по порядку роста заключена между $(n/\ln n)$ и $n$.
Библиогр. 3