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

Исследуется сложность сужений булевых функций при их реализации схемами из функциональных элементов, контактными схемами, формулами и $\pi$-схемами. Пусть $D(d)=\{D\subseteq\{0,1\}^{n}\mid|D|=d\}$. Для достаточно широкого множества значений параметра $d$ для произвольной булевой функции $f$ устанавливаются нижние оценки сложности самого сложного ее сужения на области из $D(d)$. Обсуждается связь между сложностью частичных и полностью определенных булевых функций.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 93–011–1527.