
Prikl. Diskr. Mat., 2019, Number 44, Pages 107–112
(Mi pdm664)




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
Abstract:
Genericcase 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 socalled 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, Diophantine equations.
DOI:
https://doi.org/10.17223/20710410/44/8
Full text:
PDF file (606 kB)
References:
PDF file
HTML file
Bibliographic databases:
UDC:
510.52
Citation:
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
\Bibitem{Ryb19}
\by A.~N.~Rybalov
\paper On generic undecidability of Hilbert's tenth problem for polynomial trees
\jour Prikl. Diskr. Mat.
\yr 2019
\issue 44
\pages 107112
\mathnet{http://mi.mathnet.ru/pdm664}
\crossref{https://doi.org/10.17223/20710410/44/8}
\elib{https://elibrary.ru/item.asp?id=38555965}
Linking options:
http://mi.mathnet.ru/eng/pdm664 http://mi.mathnet.ru/eng/pdm/y2019/i2/p107
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
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: 
This page:  109  Full text:  22  References:  4 
