Geodesic
On generic undecidability of Hilbert's tenth problem for polynomial trees
Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 107-112.

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

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. We study generic complexity of the Hilbert's tenth problem for systems of Diophantine equations represented by so-called polynomial trees. Polynomial tree is a binary tree, which leafs are marked by variables or the constant 1, and internal vertices are marked by operations of addition, subtraction and multiplication. Every polynomial with integer coefficients can be represented by a polynomial tree. We prove generic undecidability of the decidability problem for Diophantine equations represented by polynomial trees. To prove this theorem, we use the method of generic amplification, which allows to construct generically undecidable problems from the problems undecidable in the classical sense. The main ingredient of this method is a technique of cloning, which unites inputs of the problem together in the large enough sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.
Keywords: generic complexity
Mots-clés : Diophantine equations. 
@article{PDM_2019_2_a7,
     author = {A. N. Rybalov},
     title = {On generic undecidability of {Hilbert's} tenth problem for polynomial trees},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {107--112},
     publisher = {mathdoc},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_2_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic undecidability of Hilbert's tenth problem for polynomial trees
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 107
EP  - 112
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_2_a7/
LA  - ru
ID  - PDM_2019_2_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic undecidability of Hilbert's tenth problem for polynomial trees
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 107-112
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_2_a7/
%G ru
%F PDM_2019_2_a7
A. N. Rybalov. On generic undecidability of Hilbert's tenth problem for polynomial trees. Prikladnaâ diskretnaâ matematika, no. 2 (2019), pp. 107-112. http://geodesic.mathdoc.fr/item/PDM_2019_2_a7/

[1] 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

[2] Matiyasevich Yu. V., “Diophantineity of enumerable sets”, Doklady Akademii Nauk USSR, 191:2 (1970), 279–282 (in Russian) | Zbl

[3] Myasnikov A., Romankov V., “Diophantine cryptography in free metabelian groups: Theoretical base”, Groups, Complexity, Cryptology, 6:2 (2014), 103–120 | DOI | MR | Zbl

[4] Roman'kov V. A., “Diophantine cryptography over infinite groups”, Prikladnaya Diskretnaya Matematika, 2012, no. 2(16), 15–42 (in Russian)

[5] Roman'kov V. A., Algebraic Cryptography, OmSU Publ., Omsk, 2013 (in Russian)

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

[7] Rybalov A., “On generic undecidability of Hilbert Tenth problem”, Vestnik Omskogo Universiteta, 2011, no. 4, 19–22 (in Russian)

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

[9] Knuth D. E., The Art of Computer Programming, Addison-Wesley, Reading, Massachusetts, 1997 | MR