NP-hardness conjecture for p-adic feasibility of sparse polynomials
NP-hardness conjecture for p-adic feasibility of sparse polynomials
For a prime , let denote the class of -nomials in variables, and let be the feasibility problem for rational roots over the -adic field . The p-adic NP-hardness conjecture. For any fixed prime ,
is -hard. The analogous real feasibility problem is already known to be -hard for broader families with more than monomials, and the conjecture predicts the same phenomenon for multivariate -nomials over .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.