• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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