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

Рассматривается специальное $(s,d,\varepsilon)$-разложение произвольной булевой функции $f$, зависящей от $n$ переменных. Элементами этого разложения являются $s$, $s<n$, частичных функций, каждая из которых определена и совпадает с $f$ на некоторой области мощности $d$, где минимально возможное $d$ не более, чем в $n^3$ раз, превосходит сложность реализации функции $f$ схемами из функциональных элементов. Получены критерии существования $(s,d,\varepsilon)$-разложений и изучены их свойства.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, и ФЦП “Интеграция”, проект 473.