Немонотонная сложность как обобщение инверсионной сложности
The problem of the effective realization of Boolean functions and multi-valued logic functions by circuits in some infinite bases is considered. The bases consist of all monotone functions and finite number of non-monotone functions. The measure of the realization efficiency is non-monotone complexity. That is the number of non-monotone elements in the circuit (we assume that all monotone elements are «free»). The case of Boolean basis that consists of all monotone functions and negation function was considered by Markov. He established the exact value of the non-monotone complexity (it is also named «inversion complexity» in that case). This paper include survey of Markov theorem generalizations and several new estimations of the non-monotone complexity.