arxiv:2602.13278

NP-hardness of p-adic linear regression

Published on Feb 6

Authors:

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.

View arXiv page View PDF Add to collection

Community

Upload images, audio, and videos by dragging in the text input, pasting, or clicking here.

Tap or paste here to upload images

· Sign up or log in to comment

Upvote

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2602.13278 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2602.13278 in a dataset README.md to link it from this page.

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2602.13278 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.