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^{[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, (), 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, () · Zbl 0793.03066
[6] Canny, J., Some algebraic and geometric computations in PSPACE, (), 460-467
[7] characteristic polynomials, Generalized, J. symbolic computation, J. symbolic computation, 9, 241-250, (1990)
[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)
[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, (), 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, (), 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, (), 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, (), 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. 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.