Точное значение немонотонной сложности булевых функций

Математические заметки. 2019. Т. 105. № 1. С. 32–41.

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

Исследуется задача о сложности реализации булевых функций схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования) и конечное число немонотонных функций единичного веса. Для сложности реализации булевых функций в случае, когда  единственным немонотонным элементом базиса является отрицание, исчерпывающее описание  было получено А.А. Марковым: минимальное число отрицаний, достаточное для реализации произвольной булевой функции f (инверсионная сложность функции f), равно ]log2(d(f)+1)[, где d(f) — максимальное  (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с 1 на 0.

В данной работе этот результат обобщен на случай вычисления булевых функций над произвольным базисом B указанного вида. Установлено, что минимальное число немонотонных функций, достаточное для вычисления произвольной булевой функциии f, равно  ]log2(d(f)/D(B)+1)[, где D(B) = max d(ω), максимум берется по всем немонотонным функциям ω базиса B.

 

Ключевые слова: схемная сложность, Boolean circuits, булевы схемы, inversion complexity, инверсионная сложность, nonmonotone complexity, немонотонная сложность, logic circuits, схемы из функциональных элементов, логические схемы, negation compelexity