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

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 ⁣(nNFn,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.

Sources & referencesView supporting material

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.