Abstract <p> We study the computational complexity of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation>-adic linear regression: given data <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\((x_i,y_i)\)</EquationSource> </InlineEquation> with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(x_i\in\mathbb{Q}^n\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(y_i\in\mathbb{Q}\)</EquationSource> </InlineEquation>, find coefficients <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\beta\in\mathbb{Q}^n\)</EquationSource> </InlineEquation> minimising the <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation>-adic residual sum <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(L(\beta)=\sum_{i=1}^{r} \lvert y_i-x_i^\top\beta\rvert_p\)</EquationSource> </InlineEquation>. Here <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(r\)</EquationSource> </InlineEquation> is the number of observations. Unlike least-squares and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\ell_1\)</EquationSource> </InlineEquation> regression over <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\mathbb{R}\)</EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\{0,1\}\)</EquationSource> </InlineEquation> without increasing loss, and each edge contributes <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(0\)</EquationSource> </InlineEquation> to the loss exactly when it crosses the induced cut. Hence minimising <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(L(\beta)\)</EquationSource> </InlineEquation> is equivalent to maximising the cut size. Our result complements existing tractable regimes for <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation>-adic regression (e.g., polynomial-time solvability in fixed dimension by enumerating hyperplanes through <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(n{+}1\)</EquationSource> </InlineEquation> data points) and motivates studying approximation, parameterised complexity, and alternative aggregations of <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation>-adic residuals. </p>

Expressivity and NP-Hardness of \(p\)-Adic Linear Regression

期刊论文
发表日期：

2026年5月6日

查看全文

Greg Baker

摘要

Abstract

We study the computational complexity of \(p\) -adic linear regression: given data \((x_i,y_i)\) with \(x_i\in\mathbb{Q}^n\) and \(y_i\in\mathbb{Q}\) , find coefficients \(\beta\in\mathbb{Q}^n\) minimising the \(p\) -adic residual sum \(L(\beta)=\sum_{i=1}^{r} \lvert y_i-x_i^\top\beta\rvert_p\) . Here \(r\) is the number of observations. Unlike least-squares and \(\ell_1\) regression over \(\mathbb{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(\beta)\) 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.