On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals (Q1185456): Difference between revisions

This is the first of a series of three papers devoted to the complexity of elementary algebra (decision problem and quantifier elimination for the reals). It begins with some history of the progress concerning the complexity bounds for the decision or quantifier elimination algorithms. The main point is the dependance in the number of variables. Consider a formula in prenex form, \(Q_ 1x^{[1]}\dots Q_ \omega x^{[\omega]}P(x^{[0]},x^{[1]},\dots,x^{[\omega]})\), where the \(x^{[i]}\) are vectors of \(n_ i\) variables and two successive quantifiers \(Q_ i\) and \(Q_{i+1}\) are different; let \(n=\sum_{i=0}^ \omega n_ i\) be the total number of variables, free and bound. \textit{G. E. Collins's} [Autom. Theor. form. Lang., 2nd int. Conf., Kaiserslautern 1975, Lect. Notes Comput. Sci. 33, 134-183 (1975; Zbl 0318.02051)] algorithm, using cylindrical algebraic decomposition, had an operation bound doubly exponential in the total number of variables: the exponent in his bound was \(2^{O(n)}\). Then \textit{D. Yu. Grigoriev} [J. Symb. Comput. 5, 65-108 (1988; Zbl 0689.03021)] described an algorithm for decision doubly exponential in the number of alternation of quantifiers: the exponent was \(O(n)^{O(\omega)}\); this feature was also obtained for quantifier elimination by \textit{Heintz}, \textit{Roy} and \textit{Solerno} [Bull. Soc. Math. France 118, 101-126 (19??)]. For the algorithms presented by Renegar, the exponent in the bound takes into account the size of the different blocks of variables: it is \(\prod_{i=0}^ \omega n_ i\). It is also shown that these algorithms are well parallelizable. This first paper in the series deals with the problem of deciding the existence of a solution to a system of polynomial equations and inequalities in several variables. The main point is to reduce the multivariate problem to a univariate one; this is done by using a variant of the \(u\)-resultant. This gives a uniform procedure which, starting from a list \(g\) of polynomials in \(n\) variables, produces a list \({\mathcal R}(g)\) of univariate polynomials from which one can obtain at least one point for each maximal connected subset of \(\mathbb{R}^ n\) where each polynomial of \(g\) has a constant sign \((+,-,0)\) (these form the so called connected sign partition of \(g\)). Then, for the univariate problem, the algorithm of \textit{M. Ben Or}, \textit{D. Kozen} and \textit{J. Reif} [J. Comput. Syst. Sci. 32, 251-264 (1986; Zbl 0634.03031)] is used.