Scholarlink

<p>From the negative solution to Hilbert’s tenth problem it follows that there exist polynomials p(<i>a</i>, <i>x</i><sub>1</sub>, . . . , <i>x</i><sub><i>n</i></sub>) with integer coefficients such that there is no algorithm that, for any natural number a determines whether the equation <i>p</i>(<i>a</i>, <i>x</i><sub>1</sub>, . . . , <i>x</i><sub><i>n</i></sub>) = 0 has 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Generic Complexity of Diophantine Problem in Parametric Form

  • 期刊论文

  • 发表日期：

    2025年2月1日

查看全文
  • A. N. Rybalov

摘要

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) = 0 has 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.