Prikl. Diskr. Mat., 2019, Number 44, Pages 107–112
This article is cited in 1 scientific paper (total in 1 paper)
Mathematical Backgrounds of Informatics and Programming
On generic undecidability of Hilbert's tenth problem for polynomial trees
A. N. Rybalov
Sobolev Institute of Mathematics, Omsk, Russia
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.
generic complexity, Diophantine equations.
PDF file (606 kB)
A. N. Rybalov, “On generic undecidability of Hilbert's tenth problem for polynomial trees”, Prikl. Diskr. Mat., 2019, no. 44, 107–112
Citation in format AMSBIB
\paper On generic undecidability of Hilbert's tenth problem for polynomial trees
\jour Prikl. Diskr. Mat.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. V. Seliverstov, “Dvoichnye resheniya dlya bolshikh sistem lineinykh uravnenii”, PDM, 2021, no. 52, 5–15
|Number of views:|