The complexity of elementary algebra and geometry (Q1096620): Difference between revisions

The main contribution of the paper is an efficient decision procedure for the complexity of deciding consistency, over the field \(\mathbb{R}\) of real numbers, of a system of \(n\) univariate equations and inequalities (strict and non-strict) with coefficients in a computable subring of \(\mathbb{R}\). Details of this procedure form a basis for modern algorithms in real algebraic geometry, [\textit{S. Basu} et al., Algorithms in real algebraic geometry. Berlin: Springer (2006; Zbl 1102.14041)]. The algorithm is shown to be in the complexity class NC, i.e., given by a uniform family of circuits of depth \((\log n)^{O(1)}\) and size \(n^{O(1)}\). An attempt then is made in the paper to extend the result to the multivariate setting, claiming single-exponential space upper bounds. However it was found to be incorrect. To quote [\textit{J. Renegar}, J. Symb. Comput. 13, No. 3, 255--299 (1992; Zbl 0763.68042)], p.259: ``Unfortunately, a flaw was found in their complexity analysis. It is now apparent that the algorithm exactly as presented in Ben-Or et al.(1986) cannot achieve the claimed results for sentences with more than one variable.'' Doubly exponential upper bounds were obtained later in [\textit{N. Fitchas} et al., Publ. Math. Univ. Paris VII 32, 103--145 (1990; Zbl 0704.03014)] (see [\textit{J. Renegar}, J. Symb. Comput. 13, No. 3, 255--299 (1992; Zbl 0763.68042); \textit{S. Basu}, Panor. Synth. 51, 107--153 (2017; Zbl 1398.14062)] for a discussion). Editorial remark: Originally, in the volume 641 in 1988, a review of M. Tetruashvili identical to his earlier submission to MathSciNet \url{https://mathscinet.ams.org/mathscinet-getitem?mr=851192} was printed, apparently without notification of the coincidence. To indicate the flaws of the paper which became known since then, and to rectify the situation, this was replaced in 2021 by the second review given here.