On Generic Complexity of Diophantine Problem in Parametric Form Full article
| Journal |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||
|---|---|---|---|
| Output data | Year: 2025, Volume: 64, Number: 1, Pages: 47-54 Pages count : 8 DOI: 10.1007/s10469-026-09811-x | ||
| Tags | Diophantine equations, Hilbert’s tenth problem, generic solvability, generic algorithms, polynomial time, undecidable problems, parametric problems | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 22-11-20019 |
Abstract:
From the negative solution to Hilbert’s tenth problem it follows that there exist polynomials p(a,x1,...,xn) with integer coefficients such that there is no algorithm that, for any natural number a determines whether the equation p(a,x1,...,xn)=0has a solution in integers. Professor V. A. Romankov posed to the author the question whether this Diophantine problem in parametric form is generically decidable. Generic algorithms decide problems on sets of almost all inputs, providing an indefinite answer for the remaining rare inputs. We prove that for some polynomials p this problem can be undecidable in the classical sense, but generically decidable, whereas for others it remains generically undecidable.
Cite:
Rybalov A.N.
On Generic Complexity of Diophantine Problem in Parametric Form
Algebra and Logic. 2025. V.64. N1. P.47-54. DOI: 10.1007/s10469-026-09811-x WOS Scopus OpenAlex
On Generic Complexity of Diophantine Problem in Parametric Form
Algebra and Logic. 2025. V.64. N1. P.47-54. DOI: 10.1007/s10469-026-09811-x WOS Scopus OpenAlex
Dates:
| Submitted: | Apr 22, 2024 |
| Accepted: | Sep 18, 2024 |
Identifiers:
| ≡ Web of science: | WOS:001679846700001 |
| ≡ Scopus: | 2-s2.0-105029291490 |
| ≡ OpenAlex: | W7127926234 |