Нахождение множеств переменных частичной булевой функции, достаточных для её реализации в классах, задаваемых предикатами

Для заданного класса $K$ частичных булевых функций и произвольной частичной булевой функции $f$ от $n$ переменных множество $U$ её переменных называется достаточным для реализации в классе $K,$ если в этом классе найдётся функция, доопределяющая $f$ и зависящая от переменных из множества $U$. В статье рассматривается задача нахождения всех множеств, достаточных для реализации функции $f$ в классе $K$. Для ряда классов, задаваемых отношениями, предлагаются алгоритмы, решающие указанную задачу со сложностью $O(2^nn^2)$ битовых операций. В том числе построены алгоритмы указанной сложности для классов $P_2^*$ всех частичных булевых функций и $M_2^*$ всех частичных монотонных функций. Предлагаемые алгоритмы основаны на использовании преобразований Уолша–Адамара и Мёбиуса. Библиогр. 21.