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
Author:
- James RenegarJRJames Renegar
Open Access
- 1 March 1992
- journal article
- Published by Elsevier in Journal of Symbolic Computation
- Vol. 13 (3) , 255-299
Abstract
No abstract availableKeywords
This publication has 20 references indexed in Scilit:
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- A bibliography of quantifier elimination for real closed fieldsJournal of Symbolic Computation, 1988
- 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