On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae
Author:
- James RenegarJRJames Renegar
- 1 December 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (6) , 1008-1025
Abstract
Upper bounds on the complexity of approximating solutions of general algebraic formulae over the real numbers are established; included are systems of polynomial equations and inequalities.Keywords
This publication has 20 references indexed in Scilit:
- On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier eliminationJournal of Symbolic Computation, 1992
- On the computational complexity and geometry of the first-order theory of the reals. Part II: The general decision problem. Preliminaries for quantifier eliminationJournal of Symbolic Computation, 1992
- 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 realsJournal of Symbolic Computation, 1992
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic setsJournal 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
- On computing the determinant in small parallel time using a small number of processorsInformation Processing Letters, 1984
- Resolution des systemes d'equations algebriquesTheoretical Computer Science, 1981
- On Euclid's Algorithm and the Theory of SubresultantsJournal of the ACM, 1971