Geodesic
On binary solutions to systems of equations
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 26-32

Voir la notice de l'article provenant de la source Math-Net.Ru

A solution is called binary if each variable is equal to either zero or one. It is well known that it is hard to find a binary solution to the system of algebraic equations in which the coefficients are integers with small absolute values. The aim of the paper is to propose an effective probabilistic reduction of the system to a new equation when there is a small difference between the number of binary solutions to the first equation and the number of binary solutions to the entire system. The proposed method is based on replacing the given system of equations with a linear combination of these equations. Coefficients are random integers that are independently and uniformly distributed over the segment from zero to some upper bound. The bound depends on the number of redundant binary solutions to the first equation that do not serve as solutions to the entire system. The proof uses the Schwartz–Zippel lemma. Moreover, if the first equation is linear, then there exists a pseudo-polynomial time algorithm to check the correctness of the reduction to the new equation in the general case.
Mots-clés : algebraic equation
Keywords: probabilistic algorithm, computational complexity. 
@article{PDM_2019_3_a3,
     author = {A. V. Seliverstov},
     title = {On binary solutions to systems of equations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {26--32},
     publisher = {mathdoc},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a3/}
}
TY  - JOUR
AU  - A. V. Seliverstov
TI  - On binary solutions to systems of equations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 26
EP  - 32
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a3/
LA  - ru
ID  - PDM_2019_3_a3
ER  - 
%0 Journal Article
%A A. V. Seliverstov
%T On binary solutions to systems of equations
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 26-32
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a3/
%G ru
%F PDM_2019_3_a3
A. V. Seliverstov. On binary solutions to systems of equations. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 26-32. http://geodesic.mathdoc.fr/item/PDM_2019_3_a3/