Немонотонная сложность логических схем и близкие задачи

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