Expressivity and NP-Hardness of p-Adic Linear Regression

We study the computational complexity of p -adic linear regression: given data (xᵢ, yᵢ) with xᵢⁿ and yᵢ, find coefficients ⁿ minimising the p -adic residual sum L () =₈=₁^r yᵢ-xᵢ^ₚ. Here r is the number of observations. Unlike least-squares and ₁ regression over R, the ultrametric inequality produces a discrete, hierarchical loss landscape in which small perturbations can change divisibility patterns abruptly. We show that this discretisation has worst-case computational consequences: computing an optimal p -adic regression solution is nondeterministic polynomial-time (NP) -hard. The proof is by a polynomial-time reduction from the maximum cut (Max-Cut) problem. We construct a regression instance in which the coefficients corresponding to vertices can be rounded to \0, 1\ without increasing loss, and each edge contributes 0 to the loss exactly when it crosses the induced cut. Hence minimising L () is equivalent to maximising the cut size. Our result complements existing tractable regimes for p -adic regression (e. g. , polynomial-time solvability in fixed dimension by enumerating hyperplanes through n+1 data points) and motivates studying approximation, parameterised complexity, and alternative aggregations of p -adic residuals.