RUS  ENG
Full version
JOURNALS // Avtomatika i Telemekhanika // Archive

Avtomat. i Telemekh., 2021 Issue 9, Pages 150–168 (Mi at15632)

This article is cited 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.

Presented by the member of Editorial Board: D. E. Pal'chunov

Received: 12.01.2021
Revised: 01.03.2021
Accepted: 16.03.2021

DOI: 10.31857/S0005231021090063


 English version:
Automation and Remote Control, 2021, 82:9, 1581–1596

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024