| О генерической сложности одного варианта диофантовой проблемы | |
| Рыбалов А. Н.1 | |
| 1.1{Институт математики им. С.Л. Соболева СО РАН, Омск, Россия | |
| Дата поступления 2023.12.28 | Аннотация. Из отрицательного решения десятой проблемы Гильберта следует, что существуют многочлены $p(x_1, \ldots, x_n)$ с целыми коэффициентами такие, что нет алгоритма, который по любому натуральному числу $a$ определял бы, разрешимо ли в целых числах уравнение $p(x_1, \ldots, x_n) = a$. Профессор В.А.~Романьков задал автору вопрос о генерической разрешимости этой алгоритмической проблемы. В статье доказывается, что для некоторых таких многочленов $p$ данная проблема является генерически разрешимой, а для других -- генерически неразрешимой. |
| Ключевые слова генерическая сложность, диофантовы уравнения, амплификация | |
Библиография \bibitem{KMSS} Kapovich I., Myasnikov A., Schupp P., Shpilrain V. Generic-case complexity and decision problems in group theory // Journal of Algebra. 2003. V.~264. P.~665-694. \bibitem{Mat} Матиясевич Ю.В. Диофантовость перечислимых множеств // Доклады Академии наук СССР. 1970. Т.~191. №~2. С.~279-282. \bibitem{Ryb1} Rybalov A. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V.~5. №~1. P.~25-30. \bibitem{Ryb2} Рыбалов А.Н. О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема // Прикладная дискретная математика. 2017. №~37. С.~100-106. \bibitem{Ryb3} Рыбалов А.Н. О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев // Прикладная дискретная математика. 2019. №~44. С.~107-112. | |
Сведения о финансировании и благодарности Автор благодарит профессора Виталия Анатольевича Романькова за интересный вопрос. Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| On the generic complexity of one variant of Diophantine problem | |
| Rybalov A. N.1 | |
| 1.1Sobolev Institute of Mathematics SB RAS, Omsk, Russia | |
| Received 2023.12.28 | Abstract. From the negative solution of the tenth Hilbert's problem it follows, that there are polynomials with integer coefficients $p(x_1, \ldots, x_n)$ such that there is no algorithm deciding for all $a$ whether equation $p(x_1, \ldots, x_n) = a$ has integer solutions. Professor V.A.~Romankov asked the author a question about the generic decidability of this algorithmic problem. We prove that for some such polynomials $p$ this problem is generically decidable, but for some others it is generically undecidable. |
| Keywords {generic complexity, diophantine equations, amplyfication | |
References \bibitem{KMSS} Kapovich I., Myasnikov A., Schupp P., Shpilrain V. Generic-case complexity and decision problems in group theory // Journal of Algebra. 2003. V.~264. P.~665-694. \bibitem{Mat} Матиясевич Ю.В. Диофантовость перечислимых множеств // Доклады Академии наук СССР. 1970. Т.~191. №~2. С.~279-282. \bibitem{Ryb1} Rybalov A. Generic complexity of the Diophantine problem // Groups Complexity Cryptology. 2013. V.~5. №~1. P.~25-30. \bibitem{Ryb2} Рыбалов А.Н. О генерической сложности проблемы разрешимости систем диофантовых уравнений в форме Сколема // Прикладная дискретная математика. 2017. №~37. С.~100-106. \bibitem{Ryb3} Рыбалов А.Н. О генерической неразрешимости десятой проблемы Гильберта для полиномиальных деревьев // Прикладная дискретная математика. 2019. №~44. С.~107-112. | |
Acknowledgements Автор благодарит профессора Виталия Анатольевича Романькова за интересный вопрос. Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| Сведения об авторах Рыбалов А. Н. 1.1 |
| About the authors Rybalov A. N. 1.1 |
