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

Рассматривается сложность порождения систем булевых векторов схемами из функциональных элементов исходя из единичных векторов — генераторов схем. Изучается поведение функции Шеннона сложности порождения систем, в которых число векторов по порядку величины равно логарифму их размерности. Для рассматриваемой функции Шеннона найдена асимптотически точная формула.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 96–01–01068, и ФЦП «Интеграция», проект 473.