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].


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