NP-hardness of p-adic linear regression

arXiv:2602.13278v1 Announce Type: new
Abstract: $p$-adic linear regression is the problem of finding coefficients $beta$ that minimise $sum_i |y_i – x_i^topbeta|_p$. We prove that computing an optimal solution is NP-hard via a polynomial-time reduction from Max Cut using a regularisation gadget.