Finding connected components of a semialgebraic set in subexponential time

N. N. Vorobjov (jr.) ; D. Yu. Grigor'ev

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 5, Tome 192 (1991), pp. 3-46

Résumé

A subexponential-time algorithm is described, which finds the connected components of a semialgebraic set $\{\Xi\}\subset(\widetilde{\mathbb{Q}}_m)^n$, given by a quantifier-free formula $\Xi$ of the first-order theory of real closed fields . Here $\widetilde{\mathbb{Q}}_m$ is a real closure of the field $\mathbb{Q}_m=\mathbb{Q}(\delta_1,\dots,\delta_m)\supset\mathbb{Z}_m=\mathbb{Z}[\delta_1,\dots,\delta_m]$, $\mathbb{Q}_0=\mathbb{Q}$ and for each $1\leqq i\leqq m$ the element $\delta_i>0$ is infinitesimal relative to $\mathbb{Q}_{i-1}$. The well-known construction of the cylindrical algebraic decomposition (see [4, 5]) allows to find the connected components within exponential time. Let the formula $\Xi$ contain $k$ atomic subformulas of the form $f_i\geqq0$, $1\leqq i\leqq k$, where $f_i\in\mathbb{Z}_m[X_1,\dots,X_n]$, the absolute values of integer coefficients of $f_i$ do not exceed $M$, the degrees $\mathrm{deg}_{X_1,\dots,X_n}(f_i)$, $\mathrm{deg}_{\delta_1,\dots,\delta_m}(f_i)$ for some integers $M$, $d$, $d_0$. THEOREM. One can design an algorithm, which for $\Xi$ finds the connected components of the semialgebraic set $\{\Xi\}$ within time $M^{O(1)}(kd)^{n^{O(1)}(m+1)}d_0^{\,O(n+m)}$. The algorithm outputs each connected component by means of a certain quantifier-free formula $\Xi_i$, with $(kd)^{n^{O(1)}}$ atomic subformulas of the type $g\geqq0$, where the absolute values of integer coefficients of $g\in\mathbb{Z}_m[X_1,\dots,X_n]$ do not exceed $(M+md_0)(kd)^{n^{O(1)}}$ and the degrees $\mathrm{deg}_{X_1,\dots,X_n}(g)(kd)^{n^{O(1)}}$, $\mathrm{deg}_{\delta_1,\dots,\delta_m}(g)$. The proof of the theorem essentially involves the designed in [15] algorithm, which counts the number of connected components of $\{\Xi\}$ subexponential time and, moreover, allows for any two points of $\{\Xi\}$ to decide whether they are situated in the same connected component.