Randomized NP-completeness for p-adic rational roots of sparse polynomials in one variable

Relative to the sparse encoding, we show that deciding whether a univariate polynomial has a p-adic rational root can be done in NP for most inputs. We also prove a sharper complexity upper bound of P for polynomials with suitably generic p-adic Newton polygon. The best previous complexity upper bound was EXPTIME. We then prove an unconditional complexity lower bound of NP-hardness with respect to randomized reductions, for general univariate polynomials. The best previous lower bound assumed an unproved hypothesis on the distribution of primes in arithmetic progression. We also discuss analogous results over . Copyright 2010 ACM.

Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Randomized NP-completeness for p-adic rational roots of sparse polynomials in one variable Conference Paper