{"id":"arxiv/2602.13278","url":"https://arxiv.org/abs/2602.13278","tags":["cs.CC","math.NT"],"score":0,"title":"NP-hardness of p-adic linear regression","domain":"cs.CC","source":"arxiv","authors":["Gregory D. Baker"],"reviews":0,"subject":"cs.CC","summary":"$p$-adic linear regression is the problem of finding coefficients $β$ that minimise $\\sum_i |y_i - x_i^\\topβ|_p$. We prove that computing an optimal solution is NP-hard via a polynomial-time reduction from Max Cut using a regularisation gadget.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-06","reactions":{}}