Finding connected components of a semialgebraic set in subexponential time

DOI10.1007/BF02112426MaRDI QIDQ5905520zbMATH OpenFDO

Authors Nicolai Vorobjov, Dima Grigoriev

Publication date 27 September 1992

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02112426

zbMATH Keywords

connected components of a semialgebraic setexponential timefirst-order theory of real closed fieldssubexponential-time algorithm

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Semialgebraic sets and related spaces (14P10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

See the review in Zbl 0801.68098.

Cites work

• Constructing roadmaps of semi-algebraic sets. I: Completeness
• FOUNDATIONS OF ALGEBRAIC GEOMETRY
• scientific article; zbMATH DE number 4154415 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3893304 (Why is no real title available?)
• scientific article; zbMATH DE number 3893305 (Why is no real title available?)
• scientific article; zbMATH DE number 3346278 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On the Betti Numbers of Real Varieties
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials

Cited in

(6)

• Description of the connected components of a semialgebraic set in single exponential time
• Symmetric matrices whose entries are linear functions
• \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• scientific article; zbMATH DE number 21309 (Why is no real title available?)
• Finding connected components of a semialgebraic set in subexponential time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5905520)