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. (English) Zbl 0763.68042

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. 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 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 Heintz, Roy and 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 M. Ben Or, D. Kozen and J. Reif [J. Comput. Syst. Sci. 32, 251-264 (1986; Zbl 0634.03031)] is used.
Reviewer: M.Coste (Rennes)


68Q25 Analysis of algorithms and problem complexity
14P10 Semialgebraic sets and related spaces
03B25 Decidability of theories and sets of sentences
03C10 Quantifier elimination, model completeness, and related topics
Full Text: DOI


[1] Arnon, D. S., A bibliography of quantifier elimination for real closed fields, J. Symbolic Computation, 5, 267-274 (1988) · Zbl 0646.03024
[2] Ben-Or, M., Lower bounds for algebraic computation trees, (Proceedings of the 1983 ACM Symposium on Symbolic and Algebraic Computation (1983)), 80-86
[3] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, J. Comp. System Sci., 32, 251-264 (1986) · Zbl 0634.03031
[4] L. Shub M., Blum; Smale, S., On a theory of computation and complexity over the real numbers: NP-compIeteness, recursive functions and universal machines, Bulletin of the American Mathematical Society, 21, 1-46 (1989) · Zbl 0681.03020
[5] Blum, L.; Smale, S., The Godel incompleteness theorem and decidability over a ring, (From Topology to Computation, Proceedings of the Smalefest (1992), Springer-Verlag) · Zbl 0793.03066
[6] Canny, J., Some algebraic and geometric computations in PSPACE, (Proceedings of the 20th Annual ACM Symposium on the Theory of Computing (1988)), 460-467
[7] characteristic polynomials, Generalized, J. Symbolic Computation, J. Symbolic Computation, 9, 241-250 (1990) · Zbl 0704.12004
[8] Chistov, A. L.; D. Yu., Grigor’ev, Complexity of quantifier elimination in the theory of algebraically closed fields, Lecture Notes in Computer Science, 176, 17-31 (1984) · Zbl 0562.03015
[9] Cohen, P. J., Decision procedures for real and p-adic fields, Communications in Pure and Applied Mathematics, 22, 131-151 (1969) · Zbl 0167.01502
[10] Collins, G. E., Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Second GI Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science, 33, 134-183 (1975) · Zbl 0318.02051
[11] Csanky, L., Fast parallel matrix inversion algorithms, SIAM Journal on Computing, 5, 618-623 (1976) · Zbl 0353.68063
[12] Fitchas, N.; Galligo, A.; Morgenstern, J., Algorithmes rapides en sequential et en parallele pour l’élimination de quantificateurs en géométrie élémentaire, (Séminaire Structures Algébriques Ordonnées (1987), UER de Mathématiques Université de Paris), VII · Zbl 0704.03014
[13] Fitchas, N.; Galligo, ?.; Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields, J. Pure App. Algebra, 67, 1-14 (1990) · Zbl 0716.03023
[14] D. Yu., Grigor’ev, The complexity of the decision problem for the first order theory of algebraically closed fields, Math. USSR Izvestiya, 29, 459-475 (1987) · Zbl 0631.03006
[15] D. Yu., Grigor’ev, The complexity of deciding Tarski algebra, J. Symbolic Computation, 5, 65-108 (1988) · Zbl 0689.03021
[16] D. Yu., Grigor’ev; Vorobjov, N. N., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Computation, 5, 37-64 (1988) · Zbl 0662.12001
[17] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoretical Computer Science, 24, 239-277 (1983) · Zbl 0546.03017
[18] Heintz, J.; Roy, M.; Solernó, P., On the complexity of semialgebraic sets, (Proc. IFIP (1989), North-Holland: North-Holland San Francisco), 293-298
[19] Heintz, J.; Roy, M.; Solernó, P., Sur la complexité du principe de Tarski-Seidenberg, Bull Soc Math. France, 118, 101-126 (1990) · Zbl 0767.03017
[20] Ierardi, D., Quantifier elimination in the first-order theory of algebraically closed fields, (Proceedings of the 21st Annual ACM Symposium on the Theory of Computing (1989), Department of Computer Science: Department of Computer Science Cornell University), also PhD thesis
[21] Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[22] Khachiyan, L. G., A polynomial algorithm in linear programming, Soviet Mathematics Doklady, 20, 191-194 (1979) · Zbl 0414.90086
[23] Milnor, J., On the Betti numbers of real varieties, Proceedings of the American Mathematical Society, 15, 275-280 (1964) · Zbl 0123.38302
[24] Renegar, J., A polynomial time algorithm, based on Newton’s method, for linear programming, Mathematical Programming, 40, 59-93 (1988) · Zbl 0654.90050
[25] Renegar, J., A faster PSPACE algorithm for the existential theory of the reals, (Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science (1988)), 291-295
[26] Renegar, J., On the computational complexity of approximating solutions for real algebraic formulae, SIAM Journal on Computing (1992) · Zbl 0768.65022
[27] Renegar, J., Recent progress on the complexity of the decision problem for the reals, Proceedings of the DJMACS Workshop on Algebraic Methods in Geometric Computations (1992)
[28] Seidenberg, A., A new decision method for elementary algebra, Annals of Mathematics, 60, 365-374 (1954) · Zbl 0056.01804
[29] Steele, J. M.; Yao, A. C., Lower bounds for algebraic decision trees, J. Algorithms, 3, 1-8 (1982) · Zbl 0477.68065
[30] Tardos, É., A strongly polynomial algorithm for solving combinatorial linear programs, Operations Research, 34, 250-256 (1986) · Zbl 0626.90053
[31] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), University of California Press · Zbl 0044.25102
[32] Van Den Dries, L., Alfred Tarski’s elimination theory for real closed fields, J. Symbolic Logic, 53, 7-19 (1988) · Zbl 0651.03001
[33] Van Der Waerden, B. L., Modern Algebra (1950), Frederick Ungar Publishing Co, Vol. 2 · Zbl 0037.01903
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.