A faster PSPACE algorithm for deciding the existential theory of the reals
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 137, 291-295
- https://doi.org/10.1109/sfcs.1988.21945
Abstract
The decision problem for the existential theory of the reals is the problem of deciding if the set (x in R/sup n/; P(x) is nonempty, where P(x) is a predicate which is a Boolean function of atomic predicates either of which is a Boolean function of atomic predicates either of the form f/sub i/(x)>or=0 or f/sub j/(x)>, the f's being real polynomials. An algorithm is presented for deciding the existential theory of the reals that simultaneously achieves the best known time and space bounds. The time bound for the algorithm is slightly better than any previous bound.Keywords
This publication has 9 references indexed in Scilit:
- Complexity of deciding Tarski algebraJournal of Symbolic Computation, 1988
- Solving systems of polynomial inequalities in subexponential timeJournal of Symbolic Computation, 1988
- Some algebraic and geometric computations in PSPACEPublished by Association for Computing Machinery (ACM) ,1988
- The complexity of elementary algebra and geometryJournal of Computer and System Sciences, 1986
- Definability and fast quantifier elimination in algebraically closed fieldsTheoretical Computer Science, 1983
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- On the Betti Numbers of Real VarietiesProceedings of the American Mathematical Society, 1964
- A Decision Method for Elementary Algebra and GeometryPublished by University of California Press ,1951
- Some Formulae in EliminationProceedings of the London Mathematical Society, 1902