# zbMATH — the first resource for mathematics

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^{}\dots Q_ \omega x^{[\omega]}P(x^{},x^{},\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)

##### MSC:
 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:
##### References:
  Arnon, D.S., A bibliography of quantifier elimination for real closed fields, J. symbolic computation, 5, 267-274, (1988) · Zbl 0646.03024  Ben-Or, M., Lower bounds for algebraic computation trees, (), 80-86  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  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  Blum, L.; Smale, S., The godel incompleteness theorem and decidability over a ring, () · Zbl 0793.03066  Canny, J., Some algebraic and geometric computations in PSPACE, (), 460-467  characteristic polynomials, Generalized, J. symbolic computation, J. symbolic computation, 9, 241-250, (1990)  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  Cohen, P.J., Decision procedures for real and p-adic fields, Communications in pure and applied mathematics, 22, 131-151, (1969) · Zbl 0167.01502  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)  Csanky, L., Fast parallel matrix inversion algorithms, SIAM journal on computing, 5, 618-623, (1976) · Zbl 0353.68063  Fitchas, N.; Galligo, A.; Morgenstern, J., Algorithmes rapides en sequential et en parallele pour l’élimination de quantificateurs en géométrie élémentaire, (), VII · Zbl 0704.03014  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  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  D. Yu., Grigor’ev, The complexity of deciding Tarski algebra, J. symbolic computation, 5, 65-108, (1988) · Zbl 0689.03021  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  Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoretical computer science, 24, 239-277, (1983) · Zbl 0546.03017  Heintz, J.; Roy, M.; Solernó, P., On the complexity of semialgebraic sets, (), 293-298  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  Ierardi, D., Quantifier elimination in the first-order theory of algebraically closed fields, (), also PhD thesis  Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065  Khachiyan, L.G., A polynomial algorithm in linear programming, Soviet mathematics doklady, 20, 191-194, (1979) · Zbl 0414.90086  Milnor, J., On the Betti numbers of real varieties, Proceedings of the American mathematical society, 15, 275-280, (1964) · Zbl 0123.38302  Renegar, J., A polynomial time algorithm, based on Newton’s method, for linear programming, Mathematical programming, 40, 59-93, (1988) · Zbl 0654.90050  Renegar, J., A faster PSPACE algorithm for the existential theory of the reals, (), 291-295  Renegar, J., On the computational complexity of approximating solutions for real algebraic formulae, SIAM journal on computing, (1992) · Zbl 0768.65022  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)  Seidenberg, A., A new decision method for elementary algebra, Annals of mathematics, 60, 365-374, (1954) · Zbl 0056.01804  Steele, J.M.; Yao, A.C., Lower bounds for algebraic decision trees, J. algorithms, 3, 1-8, (1982) · Zbl 0477.68065  Tardos, É., A strongly polynomial algorithm for solving combinatorial linear programs, Operations research, 34, 250-256, (1986) · Zbl 0626.90053  Tarski, A., A decision method for elementary algebra and geometry, (1951), University of California Press · Zbl 0044.25102  Van Den Dries, L., Alfred Tarski’s elimination theory for real closed fields, J. symbolic logic, 53, 7-19, (1988) · Zbl 0651.03001  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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.