Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates

Given a class $K$ of partial Boolean functions and a partial Boolean function $f$ of $n$ variables, a subset $U$ of its variables is called sufficient for the implementation of $f$ in $K$ if there exists an extension of $f$ in $K$ with arguments in $U$. We consider the problem of recognizing all subsets sufficient for the implementation of $f$ in $K$. For some classes defined by relations, we propose the algorithms of solving this problem with complexity of $O(2^nn^2)$ bit operations. In particular, we present some algorithms of this complexity for the class $P_2^*$ of all partial Boolean functions and the class $M_2^*$ of all monotone partial Boolean functions. The proposed algorithms use the Walsh–Hadamard and Möbius transforms. Bibliogr. 21.