NP-hardness of p-adic linear regression

Gregory D. Baker

$p$-adic linear regression is the problem of finding coefficients ${\hat{I}}^2$ that minimise ${\sum }_i|y_i-x_i^{\top }{\hat{I}}^2{|}_p$. We prove that computing an optimal solution is NP-hard via a pol…