Топологическая сложность алгоритмов приближенного решения систем полиномиальных уравнений

Топологическая (или смейловская) сложность вычислительной задачи — это минимальное число ветвлений (операторов IF) в решающих эту задачу алгоритмах. В работе получены верхние и нижние оценки этого показателя для задачи приближенного решения систем полиномиальных уравнений в $\mathbf C^n$. В частности, доказано, что для основных пространств систем уравнений топологическая сложность этой задачи асимптотически (по степени уравнений) пропорциональна размерности пространства соответствующей системы.