返回Google圖書搜尋

Short Proofs for Nondivisibility of Sparse Polynomials Under the Extended Riemann Hypothesis

International Computer Science InstituteDima GrigorievM. KarpinskiAndrew M. Odlyzko

出版	International Computer Science Institute, 1991
URL	http://books.google.com.hk/books?id=Rg5uGwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS 90, KT 88, P 77a, P 77b]). The first results in this direction are due to Plaisted [P 77a, P 77b], who proved, in particular, the NP-completeness of divisibility of a polynomial x[superscript n] - 1 by a product of sparse polynomials. On the other hand, essentially nothing nontrivial is known about the complexity of the divisibility problem of two sparse integer polynomials. (One can easily prove that it is in PSPACE with the help of [M 86].) Here we prove that nondivisibility of two sparse multivariable polynomials is in NP, provided that the Extended Riemann Hypothesis (ERH) holds (see e.g. [LO 77])