On Generic Complexity of Diophantine Problem in Parametric Form | Sciact - Система учета научной деятельности ИМ СО РАН

On Generic Complexity of Diophantine Problem in Parametric Form Научная публикация

Журнал

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Вых. Данные

Год: 2025, Том: 64, Номер: 1, Страницы: 47-54 Страниц : 8 DOI: 10.1007/s10469-026-09811-x

Ключевые слова

Diophantine equations, Hilbert’s tenth problem, generic solvability, generic algorithms, polynomial time, undecidable problems, parametric problems

Авторы

Rybalov A.N. ¹

Организации

1	Omsk Division of Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Omsk, Russia

Информация о финансировании (1)

Российский научный фонд

22-11-20019

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.

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

Поступила в редакцию:	22 апр. 2024 г.
Принята к публикации:	18 сент. 2024 г.

≡ Web of science:	WOS:001679846700001
≡ Scopus:	2-s2.0-105029291490
≡ OpenAlex:	W7127926234