4
$\begingroup$

We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$?

Is it equivalent to Tarski elimination algorithm or lower?

$\endgroup$
  • $\begingroup$ By Qp you mean positive rationals? Do you have a reference? I was under the impression that it's open for (general) rationals. $\endgroup$ – Mikolas Nov 12 '17 at 1:31
  • 1
    $\begingroup$ @Mikolas Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable, but Hilbert Tenth problem over $\mathbb{Q}$ is open. $\endgroup$ – XL _At_Here_There Nov 12 '17 at 2:54
  • 1
    $\begingroup$ OK, do you have a reference for that? $\endgroup$ – Mikolas Nov 12 '17 at 12:40
  • 2
    $\begingroup$ @Mikolas I assume XL_at_China means the p-adic rationals. $\endgroup$ – Joshua Grochow Nov 12 '17 at 19:14
  • 3
    $\begingroup$ This seems to be the original reference, maybe someone can extract a running time estimate from it projecteuclid.org/euclid.bams/1183525364. $\endgroup$ – Sasho Nikolov Nov 18 '17 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.