О сложности схем в базисах, содержащих монотонные элементы с нулевыми весами

Прикладная дискретная математика. 2015. № 4. С. 24–31.

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

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

Ключевые слова: circuit complexity, схемная сложность, Boolean circuits, булевы схемы, Boolean function complexity, inversion complexity, Markov's theorem, сложность булевых функций, инверсионная сложность, теорема Маркова, logic circuits, bases with zero weight elements, схемы из функциональных элементов, базисы с нулевыми весами

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Классификация замкнутых классов функций многозначной логики, порожденных симметрическими функциями, по типам базируемости (2014)