Faster p-adic feasibility for certain multivariate sparse polynomials

We present algorithms revealing new families of polynomials admitting sub-exponential detection of p -adic rational roots, relative to the sparse encoding. For instance, we prove NP -completeness for the case of honest n -variate ( n + 1 ) -nomials and, for certain special cases with p exceeding the Newton polytope volume, constant-time complexity. Furthermore, using the theory of linear forms in p -adic logarithms, we prove that the case of trinomials in one variable can be done in NP . The best previous complexity upper bounds for all these problems were EXPTIME or worse. Finally, we prove that detecting p -adic rational roots for sparse polynomials in one variable is NP -hard with respect to randomized reductions. The last proof makes use of an efficient construction of primes in certain arithmetic progressions. The smallest n where detecting p -adic rational roots for n -variate sparse polynomials is NP -hard appears to have been unknown. ► Ultrametric analogues of recent complexity results for real sparse polynomials. ► Algorithms in NP for certain formerly multiply exponential p -adic problems. ► NP-hardness of detecting p -adic rational roots for univariate sparse polynomials. ► Short certificates for p -adic rational roots of univariate trinomials. ► Short certificates for p -adic rational roots of n -variate ( n + 1 ) -nomials.