Topological complexity and Schwarz genus of general real polynomial equation

Мы доказываем, что минимальное число ветвлений арифметических алгоритмов, приближенно решающих общее полиномиальное уравнение $x^d+a_1x^{d-1}+\dots+a_{d-1}x+a_d=0$ нечетной степени $d$, растет по меньшей мере как $\log_2d$. Эта же оценка верна для $\varepsilon$-рода вещественной алгебраической функции, соответствующей этому уравнению, то есть для минимального числа открытых множеств, покрывающих пространство $\mathbb R^d$ таких многочленов таким образом, что на каждом из этих множеств существует непрерывная функция, значение которой в каждой точке $(a_1,\dots,a_d)$ приближенно (с точностью до некоторого достаточно малого $\varepsilon>0$) равно одному из вещественных корней соответствующего уравнения.