Volume 20, No 3, 2013, P. 84100
UDC 519.71
Fedorova V. S.
On the complexity of the satisfiability problem for a system of functional Boolean equations
Abstract:
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.
Keywords: functional Boolean equation, satisfiability problem, complexity.
Fedorova Valentina Sergeevna ^{1}
1. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
email: FedorovaVS@cs.msu.ru
