Geodesic
Topological complexity and real roots of polynomials
Matematičeskie zametki, Tome 60 (1996) no. 5, pp. 670-680 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The topological complexity of an algorithm is the number of its branchings. In the paper we prove that the minimal topological complexity of an algorithm that approximately computes a root of a real polynomial of degree $d$ equals $d/2$ for even $d$, is greater than or equal to 1 for odd $d>-3$, and equals 1 for $d=3$ or 5. 
@article{MZM_1996_60_5_a2,
     author = {V. A. Vassiliev},
     title = {Topological complexity and real roots of polynomials},
     journal = {Matemati\v{c}eskie zametki},
     pages = {670--680},
     year = {1996},
     volume = {60},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1996_60_5_a2/}
}
TY  - JOUR
AU  - V. A. Vassiliev
TI  - Topological complexity and real roots of polynomials
JO  - Matematičeskie zametki
PY  - 1996
SP  - 670
EP  - 680
VL  - 60
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/MZM_1996_60_5_a2/
LA  - ru
ID  - MZM_1996_60_5_a2
ER  - 
%0 Journal Article
%A V. A. Vassiliev
%T Topological complexity and real roots of polynomials
%J Matematičeskie zametki
%D 1996
%P 670-680
%V 60
%N 5
%U http://geodesic.mathdoc.fr/item/MZM_1996_60_5_a2/
%G ru
%F MZM_1996_60_5_a2
V. A. Vassiliev. Topological complexity and real roots of polynomials. Matematičeskie zametki, Tome 60 (1996) no. 5, pp. 670-680. http://geodesic.mathdoc.fr/item/MZM_1996_60_5_a2/

[1] Smale S., “On the topology of algorithms, I”, J. Complex, 3 (1987), 81–89 | DOI | MR | Zbl

[2] Vasilev V. A., “Kogomologii grupp kos i slozhnost algoritmov”, Funktsion. analiz i ego prilozh., 22:3 (1988), 15–24 | MR | Zbl

[3] Vasilev V. A., “Topologicheskaya slozhnost algoritmov priblizhennogo resheniya sistem polinomialnykh uravnenii”, Algebra i analiz, 1:6 (1989), 98–113 | MR | Zbl

[4] Vassiliev V. A., Complements of Discriminants of Smooth Maps: Topology and Applications, Revised edition, Translations of Math. Monographs, 98, AMS, Providence, 1994