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

1992/03/01 by James Renegar · 7 citations
Computer Science · Mathematics · #Algebra over a field #Algorithm #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computation #Computational complexity theory #Computational geometry #Discrete mathematics #Mathematics #Model of computation #Order (exchange) #Polynomial and algebraic computation #Pure mathematics #Quantifier elimination

paper · pdf · doi:10.1016/s0747-7171(10)80003-3

crossref issued 1992/03/01 · crossref published 1992/03/01 · crossref published-print 1992/03/01 · openalex publication_date 1992/03/01 · crossref created 2010/06/04 · openalex created_date 2025/10/10 · crossref deposited 2025/10/10 · crossref indexed 2026/07/31 · openalex updated_date 2026/08/02

Citations

• Definability and fast quantifier elimination in algebraically closed fields
• Lower bounds for algebraic decision trees
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

Cited by

• Solving parametric polynomial systems using Generic Rational Univariate Representation
• Multivariate Sturm theory
• Constraint databases: A survey
• Queries with arithmetical constraints
• Realizability of Graphs and Linkages
• The Semialgebraic Orbit Problem
• A Generalized Framework for Virtual Substitution
• Real closed field [wikipedia]