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(β)=∑ᵢ₌₁ʳ 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.