Near NP-Completeness for Detecting p-adic Rational Roots in One Variable

Details Near NP-Completeness for Detecting p-adic Rational Roots in One Variable Near NP-Completeness for Detecting p-adic Rational Roots in One Variable

2010-01-24

arxiv.org/abs/1001.4252v1

proceedings of International Symposium on Symbolic and Algebraic Computation (ISSAC 2010, July 25-28, 2010, Munchen), pp. 331-

Mathematics

Number Theory

8 pages in 2 column format, 1 illustration. Submitted to a conference

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Near NP-Completeness for Detecting p-adic Rational Roots in One Variable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Near NP-Completeness for Detecting p-adic Rational Roots in One Variable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near NP-Completeness for Detecting p-adic Rational Roots in One Variable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-696774