Can I read Near NP-Completeness for Detecting p-adic Rational Roots in One Variable on EtoBox?

Near NP-Completeness for Detecting p-adic Rational Roots in One Variable by Avendano, Martin; Ibrahim, Ashraf; Rojas, J. Maurice; Rusek, Korben is a scholarly article available to read on EtoBox.

What is Near NP-Completeness for Detecting p-adic Rational Roots in One Variable about?

We show that deciding whether a sparse univariate polynomial has a p-adic rational root can be done in NP for most inputs. We also prove a polynomial-time upper bound for trinomials with suitably generic p-adic Newton polygon. We thus improve the best previous complexity upper bound of EXPTIME. We also 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 how our results complement analogous results over the real numbers.

Author

Avendano, Martin; Ibrahim, Ashraf; Rojas, J. Maurice; Rusek, Korben

Published

2010

Language

EN