Аннотация:

It is well known that Boolean functions have a number of different hidden structures. Some structures are of significant theoretical interest. In particular, the structures associated with the phase transition reveal important properties of the solution space of Boolean functions. Many structures are extensively used by various heuristic algorithms to prove satisfiability of Boolean functions. Among others, we can mention such structures as backdoors, backbones, blocked clauses, asymmetric tautologies, hyper binary resolvents, strongly connected components, bounded variables. Some structures are important in the context of quantum computing. In particular, we can mention the Boolean hidden shift. Typically, to effectively use hidden structures, we need to find not only the structures themselves, but also find the proper assignments for variables. In this paper, we consider the computational complexity of finding proper assignments for variables of hidden structures. In particular, we consider strongly connected components. It is well known that strongly connected components can be easily found in a Boolean function. Nevertheless, we show that the problem of finding proper assignments for the variables of strongly connected components is computationally hard.