  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.
