Geodesic
On the generic complexity of solving equations over~natural numbers with addition
Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 72-78.

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

We study the general complexity of the problem of determining the solvability of equations systems over natural numbers with the addition. The $\text{NP}$-completeness of this problem is proved. A polynomial generic algorithm for solving this problem is proposed. It is proved that if $\text{P} \neq \text{NP}$ and $\text{P} = \text{BPP}$, then for the problem of checking the solvability of systems of equations over natural numbers with zero there is no strongly generic polynomial algorithm. For a strongly generic polynomial algorithm, there is no efficient method for random generation of inputs on which the algorithm cannot solve the problem. To prove this theorem, we use the method of generic amplification, which allows us to construct generically hard problems from problems that are hard in the classical sense. The main feature of this method is the cloning technique, which combines the input data of a problem into sufficiently large sets of equivalent input data. Equivalence is understood in the sense that the problem is solved similarly for them.
Keywords: generic complexity, linear equations, natural numbers. 
@article{PDM_2024_2_a6,
     author = {A. N. Rybalov},
     title = {On the generic complexity of solving equations over~natural numbers with addition},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {72--78},
     publisher = {mathdoc},
     number = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_2_a6/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On the generic complexity of solving equations over~natural numbers with addition
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 72
EP  - 78
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_2_a6/
LA  - ru
ID  - PDM_2024_2_a6
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On the generic complexity of solving equations over~natural numbers with addition
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 72-78
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_2_a6/
%G ru
%F PDM_2024_2_a6
A. N. Rybalov. On the generic complexity of solving equations over~natural numbers with addition. Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 72-78. http://geodesic.mathdoc.fr/item/PDM_2024_2_a6/

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

[2] Gilman R. H., Myasnikov A., and Roman'kov V., “Random equations in free groups”, Groups Complexity Cryptology, 3:2 (2011), 257–284 | DOI | MR | Zbl

[3] Gilman R. H., Myasnikov A., and Roman'kov V., “Random equations in nilpotent groups”, J. Algebra, 352:1 (2012), 192–214 | DOI | MR | Zbl

[4] Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25–30 | DOI | MR | Zbl

[5] Rybalov A. and Shevlyakov A., “Generic complexity of solving of equations in finite groups, semigroups and fields”, J. Physics: Conf. Ser., 1901 (2021), 012047, 8 pp. | DOI

[6] Shevlyakov A., “Algebraic geometry over the additive monoid of natural numbers: The classifcation of coordinate monoids”, Groups Complexity Cryptology, 2:1 (2010), 91–111 | DOI | MR | Zbl

[7] Shevlyakov A. N., “Algebraic geometry over the monoid of natural numbers. Irreducible algebraic sets”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 16, no. 2, 2010, 258–269 (in Russian)

[8] Kryvyi S. L., “Compatibility of systems of linear constraints over the set of natural numbers”, Cybernetics Systems Analysis, 38:1 (2002), 17–29 | DOI | MR | Zbl

[9] Kitaev A., Shen' A., and Vyalyy M., Classical and Quantum Computations, MCCME Publ., M., 1999, 192 pp. (in Russian)

[10] Schrijver A., Theory of Linear and Integer Programming, Wiley, 1998, 484 pp. | MR | MR | Zbl