О сложности расшифровки разбиения булева куба на подкубы

Рассматривается известная задача расшифровки функций алгебры логики, то есть задача восстановления значений функции на всех наборах $n$-мерного булева куба по известным значениям на некоторых из этих наборов. В общем случае для определения функции нужно знать ее значения на всех $2^n$ наборах. Но если функция принадлежит некоторому более узкому классу, чем класс всех функций алгебры логики от $n$ переменных, то для ее определения могут потребоваться лишь значения на некотором подмножестве $n$-мерного булева куба. В данной работе рассматриваются классы функций, производящих разбиение $n$-мерного булева куба на подкубы. Получены асимптотические оценки сложности расшифровки функций из таких классов.