Polynomial-time Tractable Problems over the $p$-adic Numbers
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917989748572160 |
|---|---|
| author | Fehm, Arno Bodirsky, Manuel |
| author_facet | Fehm, Arno Bodirsky, Manuel |
| contents | We study the computational complexity of fundamental problems over the $p$-adic numbers ${\mathbb Q}_p$ and the $p$-adic integers ${\mathbb Z}_p$. Guépin, Haase, and Worrell proved that checking satisfiability of systems of linear equations combined with valuation constraints of the form $v_p(x) = c$ for $p \geq 5$ is NP-complete (both over ${\mathbb Z}_p$ and over ${\mathbb Q}_p$), and left the cases $p=2$ and $p=3$ open. We solve their problem by showing that the problem is NP-complete for ${\mathbb Z}_3$ and for ${\mathbb Q}_3$, but that it is in P for ${\mathbb Z}_2$ and for ${\mathbb Q}_2$. We also present different polynomial-time algorithms for solvability of systems of linear equations in ${\mathbb Q}_p$ with either constraints of the form $v_p(x) \leq c$ or of the form $v_p(x)\geq c$ for $c \in {\mathbb Z}$. 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 ${\mathbb Q}$ together with valuation constraints $v_p(x) \geq c$ for several different prime numbers $p$ simultaneously. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13536 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial-time Tractable Problems over the $p$-adic Numbers Fehm, Arno Bodirsky, Manuel Computational Complexity Logic F.4.1; F.2.1 We study the computational complexity of fundamental problems over the $p$-adic numbers ${\mathbb Q}_p$ and the $p$-adic integers ${\mathbb Z}_p$. Guépin, Haase, and Worrell proved that checking satisfiability of systems of linear equations combined with valuation constraints of the form $v_p(x) = c$ for $p \geq 5$ is NP-complete (both over ${\mathbb Z}_p$ and over ${\mathbb Q}_p$), and left the cases $p=2$ and $p=3$ open. We solve their problem by showing that the problem is NP-complete for ${\mathbb Z}_3$ and for ${\mathbb Q}_3$, but that it is in P for ${\mathbb Z}_2$ and for ${\mathbb Q}_2$. We also present different polynomial-time algorithms for solvability of systems of linear equations in ${\mathbb Q}_p$ with either constraints of the form $v_p(x) \leq c$ or of the form $v_p(x)\geq c$ for $c \in {\mathbb Z}$. 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 ${\mathbb Q}$ together with valuation constraints $v_p(x) \geq c$ for several different prime numbers $p$ simultaneously. |
| title | Polynomial-time Tractable Problems over the $p$-adic Numbers |
| topic | Computational Complexity Logic F.4.1; F.2.1 |
| url | https://arxiv.org/abs/2504.13536 |