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/

[1] Seliverstov A. V., “Binary solutions to some systems of linear equations”, OPTA 2018, Communications in Computer and Information Science, 871, Springer, Cham, 2018, 183–192 | DOI

[2] Schrijver A., Theory of Linear and Integer Programming, John Wiley and Sons, N.Y., 1986 | MR | MR | Zbl

[3] Smolev V. V., “On an approach to the solution of a Boolean linear equation with positive integer coefficients”, Discrete Mathematics and Applications, 3:5 (1993), 523–530 | DOI | MR | Zbl

[4] Gál A., Jang J.-T., Limaye N., et al., “Space-efficient approximations for Subset Sum”, ACM Trans. Computation Theory, 8:4 (2016), 16 | DOI | MR

[5] Bringmann K., “A near-linear pseudopolynomial time algorithm for subset sum”, SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia, 2017, 1073–1084 | DOI | MR | Zbl

[6] Koiliaris K., Xu C., “A faster pseudopolynomial time algorithm for subset sum”, SODA'17 Proc. Twenty-Eighth Ann. ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia, 2017, 1062–1072 | DOI | MR | Zbl

[7] Bateni M. H., Hajiaghayi M. T., Seddighin S., Stein C., “Fast algorithms for knapsack via convolution and prediction”, Proc. 50th Ann. ACM SIGACT Symp. on the Theory of Computing (STOC'18), ACM, N.Y., 2018, 1269–1282 | DOI | MR | Zbl

[8] Curtis V. V., Sanches C. A. A., “An improved balanced algorithm for the subset-sum problem”, Europ. J. Operat. Res., 275 (2019), 460–466 | DOI | MR | Zbl

[9] Cygan M., Mucha M., Węgrzycki K., Włodarczyk M., “On problems equivalent to $(\min,+)$-convolution”, ACM Trans. Algorithms, 15:1 (2019), 14 | DOI | MR | Zbl

[10] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[11] Rybalov A. N., “On generic complexity of decidability problem for Diophantine systems in the Skolem's form”, Prikladnaya Diskretnaya Matematika, 2017, no. 37, 100–106 (in Russian)

[12] Rybalov A. N., “On generic NP-completeness of the Boolean satisfiability problem”, Prikladnaya Diskretnaya Matematika, 2017, no. 36, 106–112 (in Russian) | DOI

[13] Rybalov A. N., “Relativized generic classes P and NP”, Prikladnaya Diskretnaya Matematika, 2018, no. 40, 100–104 (in Russian)

[14] Lyubetsky V. A., Gershgorin R. A., Gorbunov K. Yu., “Chromosome structures: reduction of certain problems with unequal gene content and gene paralogs to integer linear programming”, BMC Bioinformatics, 18:40 (2017) | DOI

[15] Schwartz J. T., “Fast probabilistic algorithms for verification of polynomial identities”, J. ACM, 27:4 (1980), 701–717 | DOI | MR | Zbl

[16] Bacher A., Bodini O., Hwang H.-K., Tsai T.-H., “Generating random permutations by coin-tossing: classical algorithms, new analysis, and modern implementation”, ACM Trans. Algorithms, 13:2 (2017), 24 | DOI | MR | Zbl