On Important Applications of Special Set Decomposition

This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.