arXiv
Open Access
2026
NP-hardness of p-adic linear regression
Gregory D. Baker
Abstrak
$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.
Penulis (1)
G
Gregory D. Baker
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2026
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓