|
This article is cited in 4 scientific papers (total in 4 papers)
Optimization, System Analysis, and Operations Research
On the number of solutions to a system of Boolean equations
V. K. Leontieva, E. N. Gordeevb a Dorodnicyn Computing Centre, Russian Academy of Sciences, Moscow, 119333 Russia
b Bauman Moscow State Technical University, Moscow, 105005 Russia
Abstract:
We consider questions concerning the solvability and the number of solutions of systems of Boolean equations. Many mathematical models arising in both operations research and cryptography are described in the language of such systems. This is due, in particular, to the fact that, in general, the problem of checking the compatibility of such systems of equations is NP-complete; therefore, the study of the qualitative properties of a system of Boolean equations provides additional information that permits one either to single out polynomially solvable particular cases or to increase the efficiency of enumeration schemes. The focus is on two aspects. The first one concerns the study of the existence and number of solutions of a Boolean equation and a system of equations when parametrizing the problem by the right-hand sides. Formulas and estimates are given for calculating this number both in general and in particular cases. Its maximum is also investigated depending on the specified parameter. The second aspect is devoted to a special case of the problem when the equation is given by the so-called continuous linear form. The properties of such forms and various criteria of continuity are studied.
Keywords:
NP-completeness, Boolean equations, Boolean programming problem, linear transformation, continuous linear form.
Citation:
V. K. Leontiev, E. N. Gordeev, “On the number of solutions to a system of Boolean equations”, Avtomat. i Telemekh., 2021, no. 9, 150–168; Autom. Remote Control, 82:9 (2021), 1581–1596
Linking options:
https://www.mathnet.ru/eng/at15632 https://www.mathnet.ru/eng/at/y2021/i9/p150
|
Statistics & downloads: |
Abstract page: | 172 | Full-text PDF : | 14 | References: | 35 | First page: | 22 |
|