Faster pp-adic feasibility for certain multivariate sparse polynomials

We present algorithms revealing new families of polynomials admitting sub-exponential detection of pp-adic rational roots, relative to the sparse encoding. For instance, we prove NP-completeness for the case of honest nn-variate (n+1)(n+1)-nomials and, for certain special cases with pp exceeding the Newton polytope volume, constant-time complexity. Furthermore, using the theory of linear forms in pp-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 pp-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 nn where detecting pp-adic rational roots for nn-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 pp-adic problems. ► NP-hardness of detecting pp-adic rational roots for univariate sparse polynomials. ► Short certificates for pp-adic rational roots of univariate trinomials. ► Short certificates for pp-adic rational roots of nn-variate (n+1)(n+1)-nomials.