NP-hardness conjecture for p-adic feasibility of sparse polynomials

About 16 years old · traced to

For a prime pp, let Fn,n+1∗{\mathcal F}^*_{n,n+1} denote the class of (n+1)(n+1)-nomials in nn variables, and let FEASQp{\text{{\tt FEAS}}}_{\mathbb{Q}_p} be the feasibility problem for rational roots over the pp-adic field Qp\mathbb{Q}_p. The p-adic NP-hardness conjecture. For any fixed prime pp,

FEASQp ⁣(⋃n∈NFn,n+1∗){\text{{\tt FEAS}}}_{\mathbb{Q}_p}\!\left(\bigcup_{n\in\mathbb{N}} {\mathcal F}^*_{n,n+1}\right)

is NP{\mathbf{NP}}-hard. The analogous real feasibility problem is already known to be NP{\mathbf{NP}}-hard for broader families with more than n+1n+1 monomials, and the conjecture predicts the same phenomenon for multivariate (n+1)(n+1)-nomials over Qp\mathbb{Q}_p.

References

Primary source

Martín Avendaño, Ashraf Ibrahim, J. Maurice Rojas and Korben Rusek, “Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials”, arXiv:1010.5310 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.