NP-hardness of p-adic linear regression
Abstract
$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.
Fields of Study & Subjects
advanced mathematical theories
Complexity and Algorithms in Graphs
Advanced Optimization Algorithms Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 6 February 2026
- Language
- EN
- Document type
- Preprint