A theorem on random polynomials and some consequences in average complexity

✍ Scribed by F. Cucker; M.-F. Roy

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 324 KB
• Volume: 10
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1016/s0747-7171(08)80052-1

✦ Synopsis

Real polynomials have very often very few real roots, and when algorithms depend on the number of real roots of polynomials rather than on their degrees, this fact has consequences on average complexity of algorithms.

In this paper we recall some classical results on the average number of real roots (which is in O(log n) where n is the degree of the polynomial for many natural random distributions) and use them to get estimates on the average complexity of various algorithms characterizing real algebraic numbers.