The complexity of elementary algebra and geometry.

*(English)*Zbl 0634.03031The 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, [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 [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 [N. Fitchas et al., Publ. Math. Univ. Paris VII 32, 103–145 (1990; Zbl 0704.03014)] (see [J. Renegar, J. Symb. Comput. 13, No. 3, 255–299 (1992; Zbl 0763.68042); 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 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.

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 [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 [N. Fitchas et al., Publ. Math. Univ. Paris VII 32, 103–145 (1990; Zbl 0704.03014)] (see [J. Renegar, J. Symb. Comput. 13, No. 3, 255–299 (1992; Zbl 0763.68042); 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 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.

Reviewer: Dmitrii Pasechnik (Oxford) (2021)

##### MSC:

14P10 | Semialgebraic sets and related spaces |

03D15 | Complexity of computation (including implicit computational complexity) |

03B25 | Decidability of theories and sets of sentences |

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

semialgebraic sets; quantifier elimination; theory of real closed fields; exponential space; NC circuit
PDF
BibTeX
XML
Cite

\textit{M. Ben-Or} et al., J. Comput. Syst. Sci. 32, 251--264 (1986; Zbl 0634.03031)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Berman, L., The complexity of logical theories, Theoret. comput. sci., 11, 71-77, (1980) · Zbl 0475.03017 |

[2] | Borodin; Hopcroft; von zur Gathen, Fast parallel matrix and gcd computations, (), 65-71 · Zbl 0507.68020 |

[3] | Borodin, A., On relating time and space to size and depth, SIAM J. comput., 6, No. 4, 733-744, (1977) · Zbl 0366.68039 |

[4] | Brown, W.; Traub, J.F., On Euclid’s algorithm and the theory of subresultants, J. assoc. comput. Mach., 18, 505-514, (1971) · Zbl 0226.65041 |

[5] | Collins, G.E., Quantifier elimination for real closed fields by cylindric algebraic decomposition, (), 134-183 |

[6] | Csanky, L., Fast parallel matrix inversion algorithms, SIAM J. comput., 5, 618-623, (1976) · Zbl 0353.68063 |

[7] | Fischer, M.J.; Rabin, M.O., Super-exponential complexity of Presburger arithmetic, () · Zbl 0319.68024 |

[8] | Marden, M., Geometry of polynomials, (1966), Amer. Math. Soc Providence · Zbl 0173.02703 |

[9] | Mayr, E.W.; Meyer, A.R., The complexity of the word problem for commutative semi-groups and polynomial ideals, Adv. in math., 46, 305-329, (1982) · Zbl 0506.03007 |

[10] | Monk, L., An elementary-recursive decision procedure for th(\(R\), +, ·), (1974), University of California Berkeley, manuscript |

[11] | Monk, L., Elementary recursive decision procedures, () |

[12] | () |

[13] | Schwartz, J.T.; Sharir, M., On the piano Mover’s problem. II. general techniques for computing topological properties of real algebraic manifolds, Adv. in appl. math, 4, 298-351, (1983) · Zbl 0554.51008 |

[14] | Tarski, A., A decision method for elementary algebra and geometry, (), 1951 · Zbl 0044.25102 |

[15] | von zur Gathen, J., Parallel algorithms for algebraic problems, (), 17-23 |

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.