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

Глава

Об оценках сложности схем в одном бесконечном базисе

С. 97-100.
В работе рассматривается задача о сложности реализации булевых функций схемами из функциональных элементов в бесконечном полном базисе, который состоит из всевозможных булевых функций, принимающих единичное значение лишь на попарно несравнимых наборах. Известны нижние оценки порядка $\sqrt n$ для сложности реализации линейной функции, функции голосования и почти всех булевых функций от $n$ переменных. Установлена верхняя оценка $n$ для сложности реализации произвольной булевой функции от $n$ переменных.