×

Additive complexity and zeros of real polynomials. (English) Zbl 0562.12020

Let \(P\in {\mathbb{R}}[X]\) be a polynomial with coefficients in the field \({\mathbb{R}}\). The additive complexity k of P is the minimal number of additions and subtractions required to compute P over \({\mathbb{R}}\). It is proved that there exists a constant C such that the number of distinct real zeros of P is \(\leq C^{k^ 2}\). The result is generalized to the additive complexity of polynomials in several variables.
Reviewer: K.Peeva

MSC:

12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
13B25 Polynomials over commutative rings
13-04 Software, source code, etc. for problems pertaining to commutative algebra
12-04 Software, source code, etc. for problems pertaining to field theory
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI