Risler, J. J. Additive complexity and zeros of real polynomials. (English) Zbl 0562.12020 SIAM J. Comput. 14, 178-183 (1985). 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 Cited in 2 ReviewsCited in 11 Documents 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 Keywords:real polynomial; additive complexity; number of distinct real zeros PDFBibTeX XMLCite \textit{J. J. Risler}, SIAM J. Comput. 14, 178--183 (1985; Zbl 0562.12020) Full Text: DOI