On the complexity of the satisfiability problem for a system of functional Boolean equations

Functional Boolean equations and the satisfiability problem for them are considered. The satisfiability problem is the following: is there any solution to the functional equation among Boolean functions? The upper and the lower bounds on the complexity of the satisfiability problem for a system of functional Boolean equations are established. This result shows that it is impossible to solve a system of functional Boolean equations by the method which has much less complexity than the method of direct enumeration. Bibliogr. 10.