Volume 20, No 3, 2013, P. 84-100
Fedorova V. S.
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.
Keywords: functional Boolean equation, satisfiability problem, complexity.
Fedorova Valentina Sergeevna 1
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia