Volume 20, No 3, 2013, P. 84-100

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. Lomonosov Moscow State University,
Leninskie gory, 119991 Moscow, Russia
e-mail: FedorovaVS@cs.msu.ru