Description of the connected components of a semialgebraic set in single exponential time

DOI10.1007/BF02573999zbMath0970.68201MaRDI QIDQ1317872

Pablo Solernó, Marie-Françoise Roy, Joos Heintz

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

zbMATH Keywords

semialgebraic setP-SPACE

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10)

Related Items

Reachability and connectivity queries in constraint databases ⋮ Numerically computing real points on algebraic sets ⋮ 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 ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ Exact Algorithms for Linear Matrix Inequalities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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