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

Статья

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

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