Counting connected components of a semialgebraic set in subexponential time
From MaRDI portal
Publication:1207337
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)
Related Items
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
