Аннотация:
Рассматривается задача получения нижних оценок для сложности реализации индивидуальных монотонных функций схемами из функциональных элементов в монотонных базисах. Основным результатом является общая оценка монотонной сложности булевой функции через некоторые ее комбинаторные характеристики. Приведен пример последовательности монотонных функции, для которых полученная оценка имеет рост $2^{n^{1/3-o(1)}}$, где $n$ — число переменных.