2026-08-18T16:06:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24132 2025-11-12T13:33:26Z ddc:004 open_access

Polynomial-Time Tractable Problems over the p-Adic Numbers Bodirsky, Manuel Fehm, Arno p-adic numbers existential theory linear theory constraint satisfaction linear program feasibility NP-hardness polynomial-time algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Arno Fehm 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.25 urn:nbn:de:0030-drops-241325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.25 eng https://creativecommons.org/licenses/by/4.0/legalcode