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

Глава

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

С. 150-152.

В работе изучается сложность реализации булевых функций схемами из функциональных элементов в двух бесконечных полных базисах. Первый базис состоит из линейных и антицепных функций от любого числа переменных. В этом базисе установлена верхняя оценка сложности реализации произвольной булевой функции от n переменных порядка (logn)*n^{1/2}. Также в этом базисе доказана нижняя оценка порядка n^{1/2} наибольшей сложности булевых функций от n переменных. Второй базис состоит из функций голосования и антицепных функций от любого числа переменных. Доказано, что в этом базисе наибольшая сложность булевых функций от n переменных по порядку роста равна logn.