TY - JOUR

T1 - Short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis

AU - Grigoriev, Dima

AU - Karpinski, Marek

AU - Odlyzko, Andrew M.

PY - 1996/12

Y1 - 1996/12

N2 - We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely related to the problem of rational interpolation. Its computational complexity was studied in [5], [4], and [6]. We prove also, somewhat surprisingly, the problem of deciding whether a rational function given by a black box equals to a polynomial belong to the parallel class NC (see, e. g., [KR 90]), provided we know the degree of its sparse representation.

AB - We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely related to the problem of rational interpolation. Its computational complexity was studied in [5], [4], and [6]. We prove also, somewhat surprisingly, the problem of deciding whether a rational function given by a black box equals to a polynomial belong to the parallel class NC (see, e. g., [KR 90]), provided we know the degree of its sparse representation.

UR - http://www.scopus.com/inward/record.url?scp=0030387031&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030387031&partnerID=8YFLogxK

U2 - 10.3233/fi-1996-283406

DO - 10.3233/fi-1996-283406

M3 - Article

AN - SCOPUS:0030387031

SN - 0169-2968

VL - 28

SP - 297

EP - 301

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 3-4

ER -