标题： 多项式时间可解问题在$p$-adic 数上 显示英文标题

标题： Polynomial-time Tractable Problems over the $p$-adic Numbers

摘要： 我们研究在$p$-adic 数${\mathbb Q}_p$和$p$-adic 整数${\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. 我们通过证明该问题对于${\mathbb Z}_3$和${\mathbb Q}_3$是 NP 完全的，但对于${\mathbb Z}_2$和${\mathbb Q}_2$属于 P 来解决他们的问题。 我们还为在${\mathbb Q}_p$中求解线性方程组的不同多项式时间算法进行了说明，这些算法要么具有形式为$v_p(x) \leq c$的约束，要么具有形式为$v_p(x)\geq c$的约束，其中$c \in {\mathbb Z}$。最后，我们展示了如何使用我们的算法在多项式时间内判断在${\mathbb Q}$上的（严格和非严格）线性不等式组以及对于多个不同的素数$p$的估值约束$v_p(x) \geq c$的可满足性。 显示英文摘要

摘要： 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\'epin, 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.