Polynomial-Time Tractable Problems over the $p$-Adic Numbers

The computational complexity for satisfiability problems of semilinear expansions of linear inequalities over $\mathbb{Q}$ (equivalently: over $ℝ)$ has been studied in [3]. The results there state that every expansion of the satisfiability problem for linear inequalities by other semilinear relations is NP-hard, unless all relations $R\subseteq {\mathbb{Q}}^n$ are essentially convex, i.e., have the property that for any two $a,b\in R$, all but finitely many rational points on the line segment between $a$ and $b$ are also contained in $R$; moreover, if all relations are essentially convex, then the satisfiability problem is in P [3, Theorem 5.2]. This result has later been generalised to expansions of linear equalities instead of inequalities [12]. Valuation constraints are clearly not essentially convex; however, they are also not semilinear, and not even semialgebraic, and hence are not covered by the results from [3] and from [12].

Different computational tasks for the $p$-adic numbers have been studied by Dolzmann and Sturm [5], and more recently by Haase and Mansutti [10]: they showed that whether a given system of linear equations with valuation constraints (where the valuation constraints in [10] are more expressive than the ones from [5], which are more expressive than ours) has a solution in ${\mathbb{Q}}_p$ for all prime numbers $p$ is in coNExpTime.

Another recent results is a polynomial-time algorithm for the dyadic feasibility problem [1], which is the problem of testing the satisfiability of systems of linear inequalities over $\mathbb{Z}[\frac{1}{2}]$; it is unclear how to reduce this problem to the problems studied here and vice versa.

Let $\tau$ be the signature $\{+,\cdot ,0,1,\pi ,\mathrm{div}\}$ where $\pi$ is a constant symbol and $\mathrm{div}$ is a binary relation symbol. Weispfenning [17] introduces a certain first-order $\tau$-theory, which he calls $T_{{\mathrm{DVF}}_p}$; both $\mathbb{Q}$ and ${\mathbb{Q}}_p$ give rise to models of $T_{{\mathrm{DVF}}_p}$ if $\pi$ is interpreted as $p$ and $a\mathrm{div}b$ if and only if . He then proves that $T_{{\mathrm{DVF}}_p}$ admits quantifier elimination for linear formulas [17, Theorem 3.6]. That is, every $\sigma$-formula, for $\sigma :=\{+,0,1,\pi ,\mathrm{div}\}$ (where the symbol for multiplication is missing, which is why these formulas are called “linear”), is over $T_{{\mathrm{DVF}}_p}$ equivalent to a quantifier-free $\sigma$-formula. Clearly, every atomic formula in the signature of ${𝔔}_p$ can be defined by a $\sigma$-formula over ${\mathbb{Q}}_p$. Let $\phi$ be a first-order sentence in the signature of ${𝔔}_p$, and let ${\phi }^{\prime }$ be the first-order $\sigma$-sentence obtained from $\phi$ by replacing all atomic formulas by their defining $\sigma$-formula. Then ${\phi }^{\prime }$ is either equivalent to $0=0$ over $T_{{\mathrm{DVF}}_p}$ or it is equivalent to $0=1$ over $T_{{\mathrm{DVF}}_p}$. It follows that either both ${𝔔}_p$ and its substructure with domain $\mathbb{Q}$ satisfy $\phi$, or both ${𝔔}_p$ and its substructure with domain $\mathbb{Q}$ satisfy $\neg \phi$, which is what we wanted to show. $◀$

By Proposition 6, these two existential theories are equal, so the claim follows from [9, Proposition 21], where it is proven that the existential theory of ${\mathbb{Q}}_p$ in a more expressive language is in NP. $◀$

Let $L:=\{x\in {\mathbb{Q}}^n:Ax=b\}$ be the solution space of the system of linear equations. If $L=\mathrm{\varnothing }$, the algorithm outputs NO. Otherwise write

with $y_1,\mathrm{\dots },y_d\in {\mathbb{Q}}^n$ linearly independent. One can check whether $L=\mathrm{\varnothing }$ and otherwise compute such $d\in \mathbb{N}$ and $y_0,\mathrm{\dots },y_d$ in polynomial time: It is possible to compute one solution $y_0\in {\mathbb{Q}}^n$ of $Ax=b$ in polynomial time [16, Corollary 3.3a]. Moreover, we can transform $A$ by elementary row operations into a matrix $A^{\prime }$ in row echelon form in polynomial time [16, Theorem 3.3], and from $A^{\prime }$ we can read off the rank $d$ of $A$ and a basis $y_1,\mathrm{\dots },y_d$ of

If $c_j=\mathrm{\infty }$ let $C_j=(\mathbb{Z}\cup \{\mathrm{\infty }\})\setminus D_j$, otherwise let $C_j=(-\mathrm{\infty },c_j]\setminus D_j$, so that the algorithm has to decide whether there exists $x\in L$ with $v_p(x_j)\in C_j$ for every $j$. If for some $j$ we have that $v_p(y_{0,j})\notin C_j$ and $y_{k,j}=0$ for every $k=1,\mathrm{\dots },d$, then every $x\in L$ satisfies $v_p(x_j)=v_p(y_{0,j})\notin C_j$, and the algorithm outputs NO. Otherwise, the algorithm outputs YES. To see that this is the correct answer, assume now that for every $j$ we have $v_p(y_{0,j})\in C_j$ or $y_{k,j}\ne 0$ for some $k$. Let $c_j^{\prime }=sup(\mathbb{Z}\setminus C_j)\in \mathbb{Z}\cup \{\mathrm{\infty }\}$, where we set $c_j^{\prime }:=\mathrm{\infty }$ if $C_j=\mathbb{Z}\cup \{\mathrm{\infty }\}$, and let

We claim that

is a solution to all the constraints. For each $j$ let

If $K_j\setminus \{0\}=\mathrm{\varnothing }$, then, by our assumption, $v_p(x_j)=v_p(y_{0,j})\in C_j$. Otherwise,

for every $k\in K_j$, so that the $v_p(p^{-2ke}{y}_{k,j})$ for $k\in K_j$ are pairwise distinct, and therefore, with $k_j:=\max K_j$,

by the choice of $e$. This shows in particular that $v_p(x_j)\in C_j$, as required. $◀$

For our second algorithm we need some preparations. As the algorithm achieves a stronger result, we just mention without proof that the usual Hermite normal form allows to check in polynomial time whether $Ax=b$ has a solution $x\in {\mathbb{Z}}_{(p)}^n$ (see, e.g., [16, Chapter 5]). However, already checking for solutions $x$ with $x_j\in {\mathbb{Z}}_{(p)}$ for $1\le j\le r$ and $x_j\in \mathbb{Q}$ for $r+1\le j\le n$ requires new ideas. Also, if we want to allow constraints of the form $v_p(x_j)\ge c_j$ rather than just $v_p(x_j)\ge 0$, one could replace $x_j$ by $x_j{p}^{-c_j}$, but only as long as $p^{c_j}$ is polynomial in the input size. This would be the case if the $c_j$ would be coded in unary, but if the $c_j$ are coded in binary, as is our convention (see above), replacing $x_j$ by $x_j{p}^{-c_j}$ will blow up the coefficients of the linear equation exponentially. We therefore do not replace $x_j$ by $x_j{p}^{-c_j}$ but instead do some extra bookkeeping, exploiting the fact that although we might not be able to compute finite sums of elements of the form $x_j{p}^{c_j}$ in polynomial time, we can at least compute their valuations.

First remove all $(a_i,c_i)$ with $a_i=0$ from the list. If $n=0$ then output $\mathrm{\infty }$. Replace each $(a_i,c_i)$ by $(a_i{p}^{-v_p(a_i)},c_i+v_p(a_i))$ to assume that $v_p(a_i)=0$. Let $c={\min }_i{c}_i$. If there exists a unique $i_0$ with $c=c_{i_0}$, then output $v_p({\sum }_i{a}_i{p}^{c_i})=c$. Otherwise assume without loss of generality that $c=c_1=c_2$. Then $a_1{p}^{c_1}+a_2{p}^{c_2}=(a_1+a_2)p^c$. Remove $(a_1,c_1)$ and $(a_2,c_2)$ from the list and append $(a_1+a_2,c)$. Repeating this process will terminate after at most $n$ steps. $◀$

We also need a certain row echelon form. Before we give the definition, we present two motivating examples.

We write ${\mathrm{GL}}_m(\mathbb{Q})$ for the general linear group of degree $m$ over the field $\mathbb{Q}$, i.e., the group of all invertible matrices in ${\mathbb{Q}}^{m\times m}$. If $\sigma \in S_n$ is a permutation, then $P_{\sigma }={({\delta }_{i,\sigma (i)})}_{i,j}\in {\mathrm{GL}}_n(\mathbb{Q})$ denotes the corresponding permutation matrix. For a pivot function $f$ and $\sigma \in S_n$, we write $f_{\sigma }$ for the pivot function given by

If $S$ is a set, then $S^{\ast }$ denotes the set of non-empty words over the alphabet $S$, i.e., the set of finite sequences of elements of $S$.

We describe how to get $U$ and $P_{\sigma }$ in terms of elementary row and column operations, where the only elementary column operations allowed are swapping two columns. If $A=0$, then we are done. Otherwise, possibly swap two rows to assume that $a_{1j}\ne 0$ for some $j$. Choose $k\in \{1,\mathrm{\dots },n\}$ such that $f_c(a_{1k},k)=\min \{f_c(a_{1j},j):j=1,\mathrm{\dots },n\}$ (which implies in particular that $a_{1k}\ne 0$, since $f_c(0,k)=\mathrm{\infty }$ by assumption). If $k\ne 1$, then swap the first column with the $k$-th column. Add multiples of the first row to the other rows to achieve that $a_{i1}=0$ for every $i>1$. Reduce the fractions in the entries of the matrix. Now take the $(m-1)\times (n-1)$-submatrix with rows $i=2,\mathrm{\dots },m$ and columns $j=2,\mathrm{\dots },n$, and iterate (extending each of the following row and column operations to the whole matrix). It is well-known that the representation size of the involved numbers stays polynomial (see, e.g., [16, Theorem 3.3]). This process terminates after at most $\max \{m,n\}$ steps, and the resulting matrix is of the desired form. $◀$

In the following, if $x\in {\mathbb{Q}}^n$ and $c\in {(\mathbb{Z}\cup \{-\mathrm{\infty }\})}^n$, we will write $v_p(x)\ge c$ if $v_p(x_j)\ge c_j$ for every $j\in \{1,\mathrm{\dots },n\}$.

The following result allows constraints of the form $v_p(x)\ge c$.

In the case $p=2$, we can additionally treat constraints of the form $v_2(x)=c$. The tuple $\delta$ encodes which constraint applies to which variable. The following is a generalisation of Theorem 17.

We can assume that if ${\delta }_j=1$ for some $j$, then $p=2$ and $c_j\ne -\mathrm{\infty }$. Define the pivot function

where we use the convention $\mathrm{\infty }+(-\mathrm{\infty }):=\mathrm{\infty }$. Clearly, $f$ is computable in polynomial time (as a function of $a$, $j$, $p$ and $c$ and $\delta$). By Lemma 15 we can compute $U$ and $P_{\sigma }$ in polynomial time such that $UA{P}_{\sigma }$ is in $f_{\sigma }$-minimal row echelon form. We may replace $A$ by $UA{P}_{\sigma }$, $b$ by $Ub$, $c$ by $P_{\sigma }^{-1}c$, and $\delta$ by $P_{\sigma }^{-1}\delta$ (adapting the idea from Remark 16 appropriately in the case $p=2$), and henceforth assume without loss of generality that $\sigma =\mathrm{id}$ and that $A$ is already in $f$-minimal row echelon form.

Let $k$ and $j_1,\mathrm{\dots },j_k$ be as in Definition 13. The algorithm then outputs YES if

1. (1)

   $b_i=0$ for every $i\in \{k+1,\mathrm{\dots },m\}$, and

2. (2)

   $v_p(a_{i{j}_i})+c_{j_i}+{\delta }_{j_i}\le v_p(b_i-{\sum }_{j\ge j_i}{\delta }_j{a}_{ij}{p}^{c_j})$ for every $i\in \{1,\mathrm{\dots },k\}$,

and otherwise it outputs NO. Note that Condition (2) can be checked in polynomial time by Lemma 10. Since $A$ is in row echelon form, Condition (1) holds if and only if there exists $x\in {\mathbb{Q}}^n$ with $Ax=b$. To see that the algorithm gives the correct answer, we have to show that (1) and (2) holds if and only if there exists $x\in {\mathbb{Q}}^n$ with $Ax=b$, $v_p(x)\ge c$ and $v_p(x_j)=c_j$ for every $j$ with ${\delta }_j=1$.

For the forward direction, we assume that (1) and (2) hold and construct $x$ as follows. For each $j\in \{1,\mathrm{\dots },n\}\setminus \{j_1,\mathrm{\dots },j_k\}$, let $x_j:=p^{c_j}$ if $c_j\in \mathbb{Z}$, and otherwise let $x_j:=0$. For $i=k,\mathrm{\dots },1$ define $x_{j_i}$ iteratively by

Since $A$ is in row echelon form, the so constructed $x$ satisfies $Ax=b$. Moreover, for each $j\notin \{j_1,\mathrm{\dots },j_k\}$ one has by definition that $v_p(x_j)\ge c_j$ and $v_p(x_j)=c_j$ if ${\delta }_j=1$, and one needs to show that the latter conditions also hold for $j\in \{j_1,\mathrm{\dots },j_k\}$, using that $A$ is in $f$-minimal row echelon form.

The full proof can be found in the arXiv-version of the paper [6]. $◀$

The primitive positive formula $\exists e,z(e+e=e\wedge y+z=e\wedge x+z\ne 0)$ defines the binary relation $\ne$ over $G$. A finite graph with vertices $[n]$ and edges $E\subseteq {[n]}^2$ can be colored with $n=|G|$ colors if and only if ${\bigwedge }_{(i,j)\in E}{x}_i\ne x_j$ is satisfiable in $G$. For $n\ge 3$, the graph coloring problem is NP-hard [7, Section 4], so the claim follows from Lemma 5. $◀$

The quotient map $\gamma :{\mathbb{Z}}_p\to {\mathbb{Z}}_p/p^e{\mathbb{Z}}_p\cong \mathbb{Z}/p^e\mathbb{Z}$ does the job: As ${\gamma }^{-1}(0)=p^e{\mathbb{Z}}_p$ is primitively positively definable in $({\mathbb{Z}}_p;+)$, also the pullback of the graph of $+$ is primitively positively definable in $({\mathbb{Z}}_p;+)$. Finally, is a primitive positive definition in of the unary relation ${\gamma }^{-1}({\ne }_0)={\mathbb{Z}}_p\setminus p^e{\mathbb{Z}}_p$. $◀$

If $p\ge 3$, then $(\mathbb{Z}/p\mathbb{Z};+,{\ne }_0)$ is NP-hard by Lemma 19. Moreover, by Lemma 20 it has a primitive positive interpretation in and so $\mathrm{CSP}({\mathbb{Z}}_p;+,{=}_0^p)$ is NP-hard by Lemma 5.

If $p$ is an arbitrary prime number, then $(\mathbb{Z}/p^2\mathbb{Z};+)$ is cyclic of order $p^2\ge 3$ and we have that $\mathrm{CSP}(\mathbb{Z}/p^2\mathbb{Z};+,{\ne }_0)$ is NP-hard by Lemma 19. The structure $(\mathbb{Z}/p^2\mathbb{Z};+,{\ne }_0)$ has a primitive positive interpretation in by Lemma 20, and hence is NP-hard by Lemma 5. $◀$

Let $c$ be a positive integer. In primitive positive formulas over structures whose signature contains $+$ and $1$, we use $cy$ as a shortcut for $\underset{c\text{ times}}{\underbrace{y+\mathrm{\cdots }+y}}$, and $c$ as a shortcut for $c1$. We also freely use the term $x+c$ for $c\in \mathbb{Z}$; if $c=0$, then this can be replaced by $x$, and if , then this can be rewritten into a proper primitive positive formula by introducing a new existentially quantified variable $y$, replacing $x+c$ by $y$, and adding a new conjunct $x=y+|c|$.