Computing the dimension of a semi-algebraic set

Рассматривается задача вычисления вещественной размерности заданного полуалгебраического подмножества $\mathbf{R}^k$, где $\mathbf{R}$ – вещественно-замкнутое поле. Доказано, что размерность $k'$ полуалгебраического множества, заданного $s$ многочленами степени $d$ от $k$ переменных, может быть вычислена за время
$$ \begin{cases} s^{(k-k')k'}d^{O(k'(k-k'))},&\text{если $k'\geqslant k/2$},\\ s^{(k-k'+1)(k'+1)}d^{O(k'(k-k'))},&\text{если $k'<k/2$}. \end{cases} $$
Этот результат слегка улучшает результат Воробьева (1999), который описал алгоритм сложности $(sd)^{O(k'(k-k'))}$ для той же задачи. Оценка на сложность алгоритма данной статьи улучшает зависимость от количества $s$ многочленов во входе. Библ. – 22 назв.