Affiliations: Dept. of Computer Science, The Pensylvania State University, University Park, PA 16802. e-mail: dima@cs.psu.edu | Department of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. e-mail: marek@cs.bonn.edu | AT&T Bell Laboratories, Murray Hill, NJ 07974. e-mail: amo@research.att.com
Note: [] Research partially supported by NFS Grant CCR-9424358.
Note: [] Research partially supported by DFG Grant KA 673/4-1, by the ESPRIT BR Grants 7097 and EC-US030.
Abstract: 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.
