Counting connected components of a semialgebraic set in subexponential time

DOI10.1007/BF01202001zbMath0900.68253MaRDI QIDQ1207337

Nikolaj N. jun. Vorob'ev, Dima Yu. Grigoriev

Publication date: 1 April 1993

Published in: Computational Complexity (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (24)

Persistent Homology of Semialgebraic Sets ⋮ Efficient simplicial replacement of semialgebraic sets ⋮ Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results ⋮ Numerically computing real points on algebraic sets ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ Divide and conquer roadmap for algebraic sets ⋮ Computing the first few Betti numbers of semi-algebraic sets in single exponential time ⋮ A baby step-giant step roadmap algorithm for general 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 ⋮ Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets ⋮ Testing elementary function identities using CAD ⋮ Hybrid Automata in Systems Biology: How Far Can We Go? ⋮ Lower bound on testing membership to a polyhedron by algebraic decision and computation trees ⋮ A numerical algorithm for zero counting. I: Complexity and accuracy ⋮ Hybrid automata, reachability, and systems biology ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ On sign conditions over real multivariate polynomials ⋮ Inclusion dynamics hybrid automata ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Computing roadmaps of semi-algebraic sets on a variety ⋮ Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials ⋮ Description of the connected components of a semialgebraic set in single exponential time ⋮ Computing real witness points of positive dimensional polynomial systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability and fast quantifier elimination in algebraically closed fields
• The complexity of elementary algebra and geometry
• Solving systems of polynomial inequalities in subexponential time
• Constructing roadmaps of semi-algebraic sets. I: Completeness
• Complexity of deciding Tarski algebra
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials

This page was built for publication: Counting connected components of a semialgebraic set in subexponential time