On generic undecidability of Hilbert's tenth problem for polynomial trees | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/8

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.