Немонотонная сложность как обобщение инверсионной сложности

XXI век: итоги прошлого и проблемы настоящего плюс. 2017. № 4(38). С. 98–105.

Михайлович А. В., Кочергин В. В.

Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только отрицание, А.А. Марковым установлено точное значение немонотонной сложности (называемой в этом случае инверсионной сложностью). В настоящей работе дан обзор результатов, обобщающих теорему Маркова, а также представлены новые оценки немонотонной сложности.

Ключевые слова: схемная сложность, inversion complexity, Markov's theorem, сложность булевых функций, инверсионная сложность, теорема Маркова, nonmonotone complexity, немонотонная сложность, logic circuits, схемы из функциональных элементов, circuit complexity, логические схемы, complexity of Boolean functions, complexity of multi-valued logic funcitons, сложность функций многозначной логики