Нижние оценки сложности сужений булевых функций

Изучается сложность сужений булевых функций при их реализации различными управляющими системами. Установлены нижние оценки для сложности самых сложных сужений на области фиксированной мощности. Показано, что в случае схем из функциональных элементов полученные оценки оптимальны по порядку. Установлено, что для каждой булевой функции от $n$ переменных, сложность реализации которой схемами из функциональных элементов превышает величину $n^{2+\varepsilon}$, $\varepsilon$ – произвольная положительная константа, найдется область в $\{0,1\}^n$, сужение на которую имеет нелинейную сложность, и эта сложность не более чем в постоянное число раз отличается от сложности самой сложной частичной функции, определенной в данной области. Доказано, что любая булева функция от $n$ переменных однозначно определяется по своим значениям не более чем в $n$ областях, мощности которых не более чем в полиномиальное (относительно $n$) число раз превосходят сложность функции.
Библиогр. 8