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


  • 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.

author list (cited authors)

  • Avendaño, M., Ibrahim, A., Rojas, J. M., & Rusek, K.

publication date

  • September 2010