Description of the connected components of a semialgebraic set in single exponential time
From MaRDI portal
Publication:1317872
DOI10.1007/BF02573999zbMath0970.68201MaRDI QIDQ1317872
Marie-Françoise Roy, Joos Heintz, Pablo Solernó
Publication date: 21 April 1994
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131293
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
14P10: Semialgebraic sets and related spaces
Related Items
Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Computing the first Betti number of a semi-algebraic set, Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials, Reachability and connectivity queries in constraint databases, Numerically computing real points on algebraic sets, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
Cites Work
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Solving systems of polynomial inequalities in subexponential time
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Counting connected components of a semialgebraic set in subexponential time
- Complexity of deciding Tarski algebra
- Construction of roadmaps in semi-algebraic sets
- Sur la complexité du principe de Tarski-Seidenberg
- Finding connected components of a semialgebraic set in subexponential time
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
