Avtomatika i Telemekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Avtomatika i Telemekhanika, 2021, Issue 9, Pages 150–168
DOI: https://doi.org/10.31857/S0005231021090063
(Mi at15632)
 

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
Full-text PDF (261 kB) Citations (4)
References:
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.
Funding agency Grant number
Russian Foundation for Basic Research 20-01-00645
This work was supported by the Russian Foundation for Basic Research, project no. 20-01-00645.
Presented by the member of Editorial Board: D. E. Pal'chunov

Received: 12.01.2021
Revised: 01.03.2021
Accepted: 16.03.2021
English version:
Automation and Remote Control, 2021, Volume 82, Issue 9, Pages 1581–1596
DOI: https://doi.org/10.1134/S000511792109006X
Bibliographic databases:
Document Type: Article
Language: Russian
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
Citation in format AMSBIB
\Bibitem{LeoGor21}
\by V.~K.~Leontiev, E.~N.~Gordeev
\paper On the number of solutions to a system of Boolean equations
\jour Avtomat. i Telemekh.
\yr 2021
\issue 9
\pages 150--168
\mathnet{http://mi.mathnet.ru/at15632}
\crossref{https://doi.org/10.31857/S0005231021090063}
\transl
\jour Autom. Remote Control
\yr 2021
\vol 82
\issue 9
\pages 1581--1596
\crossref{https://doi.org/10.1134/S000511792109006X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000716460600006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85118706800}
Linking options:
  • https://www.mathnet.ru/eng/at15632
  • https://www.mathnet.ru/eng/at/y2021/i9/p150
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Avtomatika i Telemekhanika
    Statistics & downloads:
    Abstract page:153
    Full-text PDF :1
    References:27
    First page:21
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024