On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
Open Access
- 31 March 1992
- journal article
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 13 (3) , 255-299
- https://doi.org/10.1016/s0747-7171(10)80003-3
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- Complexity of quantifier elimination in the theory of algebraically closed fieldsPublished by Springer Nature ,2005
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Complexity of deciding Tarski algebraJournal of Symbolic Computation, 1988
- Solving systems of polynomial inequalities in subexponential timeJournal of Symbolic Computation, 1988
- THE COMPLEXITY OF THE DECISION PROBLEM FOR THE FIRST ORDER THEORY OF ALGEBRAICALLY CLOSED FIELDSMathematics of the USSR-Izvestiya, 1987
- Definability and fast quantifier elimination in algebraically closed fieldsTheoretical Computer Science, 1983
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- Decision procedures for real and p‐adic fieldsCommunications on Pure and Applied Mathematics, 1969
- On the Betti numbers of real varietiesProceedings of the American Mathematical Society, 1964
- A New Decision Method for Elementary AlgebraAnnals of Mathematics, 1954