Finding connected components of a semialgebraic set in subexponential time

DOI10.1007/BF01614146zbMath0783.14036MaRDI QIDQ5966655

Nikolaj N. jun. Vorob'ev, John F. Canny, Dima Yu. Grigoriev

Publication date: 27 September 1992

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

quantifier eliminationreal closed fieldsconnected components of semialgebraic setdecidability algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Semialgebraic sets and related spaces (14P10) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (6)

Unnamed Item ⋮ Proper parametrization of real tubular surfaces ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Computing roadmaps of semi-algebraic sets on a variety ⋮ Construction of roadmaps in semi-algebraic sets ⋮ Description of the connected components of a semialgebraic set in single exponential time

Cites Work

• Definability and fast quantifier elimination in algebraically closed fields
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

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