We study the computational complexity of fundamental problems over the p-adic numbers {ℚ}_p and the p-adic integers {ℤ}_p. Guépin, Haase, and Worrell [Florent Guépin et al., 2019] proved that checking satisfiability of systems of linear equations combined with valuation constraints of the form v_p(x) = c for p ≥ 5 is NP-complete (both over {ℤ}_p and over {ℚ}_p), and left the cases p = 2 and p = 3 open. We solve their problem by showing that the problem is NP-complete for {ℤ}₃ and for {ℚ}₃, but that it is in P for {ℤ}₂ and for {ℚ}₂. We also present different polynomial-time algorithms for solvability of systems of linear equations in {ℚ}_p with either constraints of the form v_p(x) ≤ c or of the form v_p(x) ≥ c for c ∈ {ℤ}. Finally, we show how our algorithms can be used to decide in polynomial time the satisfiability of systems of (strict and non-strict) linear inequalities over {ℚ} together with valuation constraints v_p(x) ≥ c for several different prime numbers p simultaneously.

We study when the property that a field is dense in its real and p-adic closures is elementary in the language of rings and deduce that all models of the theory of algebraic fields have this property.

Abstract In [1], Anscombe and Koenigsmann give an existential ∅-definition of the ring of formal power series F[[t]] in its quotient field in the case where F is finite. We extend their method in several directions to give general definability results for henselian valued fields with finite or pseudo-algebraically closed residue fields.

We define and investigate a family of local–global principles for fields involving both orderings and p -valuations. This family contains the PAC, PRC and P p C fields and exhausts the class of pseudo classically closed fields. We show that the fields satisfying such a local–global principle form an elementary class, admit diophantine definitions of holomorphy domains, and their orderings satisfy the strong approximation property.

Abstract The work [11] deals with questions of first-order definability in algebraic function fields. In particular, it exhibits new cases in which the field of constant functions is definable, and it investigates the phenomenon of definable transcendental elements. We fix some of its proofs and make additional observations concerning definable closure in these fields.