Решение систем полиномиальных неравенств над вещественно замкнутым полем в субэкспоненциальное время

Обозначим через $\mathbb{Q}_m=\mathbb{Q}(\delta_1,\dots,\delta_m)$ упорядоченное поле, где $\delta_{i+1}>0$ является бесконечно малым относительно элементов поля $\mathbb{Q}_i$, $0\leqslant i<m$, (положим $\mathbb{Q}_0=\mathbb{Q}$). Пусть дана система неравенств $f_1>0,\dots,f_s>0$, $f_{s+1}\geqslant0,\dots,f_k\geqslant0$, где многочлены $f_j\in\mathbb{Q}_m[X_1,\dots,X_n]$ удовлетворяют следующим оценкам: степени $\mathrm{deg}_{\delta_1,\dots,\delta_m}(f_j)<d_0$, $\mathrm{deg}_{X_1,\dots,X_n}(f_j)<d$ и абсолютная величина всякого целого числа, входящего в коэффициенты многочленов $f_j$, не превосходит $2^{M}$. Построен алгоритм, который проверяет разрешимость данной системы неравенств над вещественным замыканием поля $\mathbb{Q}_m$ за время полиномиальное от $M$, $((kd)^nd_0)^{n+m}$. В случае поля $\mathbb{Q}_m=\mathbb{Q}$ алгоритм строит явно некоторое семейство вещественных решений системы (если она совместна). Известные ранее алгоритмы для этой задачи имели сложность порядка $M(kd\,d_0^m)^{2O(n)}$. Библ. – 21 назв.