<p>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}$?</p>

<p>Is it equivalent to Tarski elimination algorithm or lower?</p>

CC BY-SA 3.0
2017-11-12T01:31:26.503Z
By Qp you mean positive rationals? Do you have a reference? I was under the impression that it's open for (general) rationals.
Mikolas
CC BY-SA 3.0
2017-11-12T02:54:49.143Z
@Mikolas Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable, but Hilbert Tenth problem over $\mathbb{Q}$ is open.
XL _At_Here_There
CC BY-SA 3.0
2017-11-12T12:40:10.443Z
OK, do you have a reference for that?
Mikolas
CC BY-SA 3.0
2017-11-12T19:14:59.180Z
@Mikolas I assume XL_at_China means the p-adic rationals.
Joshua Grochow
CC BY-SA 3.0
2017-11-13T02:10:49.297Z
@Mikolas  https://math.mit.edu/~poonen/slides/h10.pdf
XL _At_Here_There
CC BY-SA 3.0
2017-11-18T18:28:22.553Z
This seems to be the original reference, maybe someone can extract a running time estimate from it https://projecteuclid.org/euclid.bams/1183525364.
Sasho Nikolov
CC BY-SA 3.0
2017-11-22T17:52:39.463Z
@SashoNikolov More precisely, the paper shows solvability of Hilbert’s 10th problem over $\mathbb Z_p$, rather than just $\mathbb Q_p$. But anyway, as far as I can see, one cannot get any estimates from the paper: the given algorithm just dovetails two infinite threads, one looking for a counterexample ($n$ such that the polynomial has no root modulo $p^n$), and one looking for a zero of the polynomial with all components algebraic over $\mathbb Q$. (The nontrivial part of the paper is to show that this is enough, and that $\mathbb Z_p\cap\tilde{\mathbb Q}$ is indeed enumerable.)
Emil Jeřábek
CC BY-SA 3.0
2017-11-22T18:41:22.420Z
Note that the problem is equivalent to the complexity of the existential theory of $\mathbb Q_p$. I have a hard time finding reliable information on the computational complexity of the first-order theory of $\mathbb Q_p$ or its existential fragment; in particular, it is claimed in Egidi, "The complexity of the theory of p-adic numbers" (1993) that the theory is decidable in doubly exponential space, but this claim is apparently retracted in Egidi, "A quantifier elimination for the theory of p-adic numbers" (1998), where the author says that the best known algorithm is non-elementary, ...
Emil Jeřábek
CC BY-SA 3.0
2017-11-22T18:43:47.760Z
... due to Cohen, "Decision procedures for real and p-adic fields" (1969). The only known lower bound is that the theory is hard for alternating exponential time with linear number of alternations, due to Berman. However, this is for the *full* first-order theory. The existential theory is likely to have smaller complexity (for example, the existential theory of $\mathbb R$ is in PSPACE).
Emil Jeřábek
<cc.complexity-theory><reference-request><comp-number-theory>
What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$
XL _At_Here_There
# What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

(Asked by: username_0 on 2017-11-11)

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?

**Tags:** cc.complexity-theory, reference-request, comp-number-theory

> **Comments:**
> **username_1**: By Qp you mean positive rationals? Do you have a reference? I was under the impression that it's open for (general) rationals.  
> **username_0**: @username_1 Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable, but Hilbert Tenth problem over $\mathbb{Q}$ is open.  
> **username_1**: OK, do you have a reference for that?  
> **username_2**: @username_1 I assume XL_at_China means the p-adic rationals.  
> **username_0**: @username_1  https://math.mit.edu/~poonen/slides/h10.pdf  
> **username_3**: This seems to be the original reference, maybe someone can extract a running time estimate from it https://projecteuclid.org/euclid.bams/1183525364.  
> **username_4**: @SashoNikolov More precisely, the paper shows solvability of Hilbert’s 10th problem over $\mathbb Z_p$, rather than just $\mathbb Q_p$. But anyway, as far as I can see, one cannot get any estimates from the paper: the given algorithm just dovetails two infinite threads, one looking for a counterexample ($n$ such that the polynomial has no root modulo $p^n$), and one looking for a zero of the polynomial with all components algebraic over $\mathbb Q$. (The nontrivial part of the paper is to show that this is enough, and that $\mathbb Z_p\cap\tilde{\mathbb Q}$ is indeed enumerable.)  
> **username_4**: Note that the problem is equivalent to the complexity of the existential theory of $\mathbb Q_p$. I have a hard time finding reliable information on the computational complexity of the first-order theory of $\mathbb Q_p$ or its existential fragment; in particular, it is claimed in Egidi, "The complexity of the theory of p-adic numbers" (1993) that the theory is decidable in doubly exponential space, but this claim is apparently retracted in Egidi, "A quantifier elimination for the theory of p-adic numbers" (1998), where the author says that the best known algorithm is non-elementary, ...  
> **username_4**: ... due to Cohen, "Decision procedures for real and p-adic fields" (1969). The only known lower bound is that the theory is hard for alternating exponential time with linear number of alternations, due to Berman. However, this is for the *full* first-order theory. The existential theory is likely to have smaller complexity (for example, the existential theory of $\mathbb R$ is in PSPACE).  

---

## 0 answers

