Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials

Details Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials

2010-10-26

arxiv.org/abs/1010.5310v2

Mathematics

Number Theory

31 pages, 3 figures, submitted for publication. This version corrects various typos and clarifies the proof of Assertion (3)(c

Scientific paper

We present algorithms revealing new families of polynomials allowing sub-exponential detection of p-adic rational roots, relative to the sparse encoding. For instance, we show that the case of honest n-variate (n+1)-nomials is doable in NP and, for p exceeding the Newton polytope volume and not dividing any coefficient, in constant time. Furthermore, using the theory of linear forms in p-adic logarithms, we prove that the case of trinomials in one variable can be done in NP. The best previous complexity bounds for these problems were EXPTIME or worse. Finally, we prove that detecting p-adic rational roots for sparse polynomials in one variable is NP-hard with respect to randomized reductions. The last proof makes use of an efficient construction of primes in certain arithmetic progressions. The smallest n where detecting p-adic rational roots for n-variate sparse polynomials is NP-hard appears to have been unknown.

Affiliated with

Also associated with

No associations

Rating

Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials 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 Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster p-adic Feasibility for Certain Multivariate Sparse Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159091