## Complexity of computing semi-algebraic descriptions of the connected components of a semialgebraic set.(English)Zbl 0960.14033

Gloor, Oliver (ed.), Proceedings of the 1998 international symposium on symbolic and algebraic computation, ISSAC ’98, Rostock, Germany, August 13-15, 1998. New York, NY: ACM Press. 25-29 (1998).
Let $$P_1,\dots,P_s \in\mathbb{Q}[x_1,\dots,x_k]$$ be polynomials of degree bounded by $$d$$ and logarithmic height bounded by $$\tau$$. The main outcome of the paper can be paraphrased as the description of a (uniform, deterministic, sequential) algorithm $$\beta$$ which outputs a semialgebraic description of all connected components of all semialgebraic subsets of $$\mathbb{R}^k$$ defined by arbitrary consistent sign conditions on the polynomials $$P_1,\dots,P_s$$. The polynomials appearing in the output have degree and logarithmic height bounded by $$d^{O(k^2)}$$ and $$d^{O(k^2)} \tau$$ respectively. The total number of arithmetic operations (in $$\mathbb{Q}$$) and of bit operations used by the algorithm $$\beta$$ is bounded by $$s^{k+1}d^{O(k^3)}$$ and $$s^{k+1}d^{O(k^3)}\tau^{O(1)}$$, respectively (theorem 3). This is a dramatic improvement over the best previously known complexity bounds for this task. These bounds are of order $$(s d)^{k^c}$$ and $$(s d)^{k^c}\tau^{O(1)}$$ with a constant $$c$$ considerably higher than three [see J. Heintz, M.-F. Roy and P. Solerno, C. R. Acad. Sci., Paris, Sér. I 313, No. 4, 167-170 (1991; Zbl 0764.14024), Discrete Comput. Geom. 11, No. 2, 121-140 (1994) and J. Canny, D. Yu. Grigor’ev and N. N. Vorob’ev jun., Appl. Algebra Eng. Commun. Comput. 2, No. 4, 217-238 (1992; Zbl 0783.14036)]. As a consequence of their main result, the authors obtain similar complexity bounds for the decomposition of a semialgebraic set defined by an arbitrary quantifier free formula containing only the polynomials $$P_1,\dots,P_s$$ (theorem 2) and a $$d^{O(k^3)}\tau^{O(1)}$$ bit complexity bound in the case of a hypersurface defined by a single polynomial of degree $$d$$ and logarithmic height $$\tau$$, i.e. in the case $$s=1$$ (theorem 1). The proof follows the general lines of the main algorithm of the paper by J. Heintz, M.-F. Roy and P. Solerna in Discrete Comput. Geom. cited above, using sensitive complexity improvements for certain subroutines [see S. Basu, R. Pollack and M.-F. Roy, J. Am. Math. Soc. 13, No. 1, 55-82 (2000; Zbl 0933.14037) and J. Complexity 13, No. 1, 28-37 (1997; Zbl 0872.68050)] and adding new arguments of the same spirit.
For the entire collection see [Zbl 0903.00083].

### MSC:

 14Q15 Computational aspects of higher-dimensional varieties 14P10 Semialgebraic sets and related spaces 68Q25 Analysis of algorithms and problem complexity

### Keywords:

semialgebraic set; connected component; complexity

### Citations:

Zbl 0764.14024; Zbl 0783.14036; Zbl 0933.14037; Zbl 0872.68050