Topological complexity and real roots of polynomials

被引：1

作者：

Vassiliev, VA

机构：

[1] RUSSIAN ACAD SCI,VA STEKLOV MATH INST,MOSCOW 117901,RUSSIA

[2] INDEPENDENT MOSCOW UNIV,MOSCOW,RUSSIA

来源：

MATHEMATICAL NOTES | 1996年 / 60卷 / 5-6期

关键词：

number of branchings of an algorithm; topological complexity; real roots of a polynomial; approximate real root;

D O I：

10.1007/BF02309164

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 greater than or equal to 3, and equals 1 for d = 3 or 5.

引用

页码：503 / 509

页数：7