Determination of the connected components of a semialgebraic set in subexponential time

MaRDI QIDQ3364033zbMATH OpenFDO

Authors Nicolai Vorobjov, Dima Grigoriev

Publication date 1991

zbMATH Keywords

exponential timesubexponential-time algorithmconnected components of a semialgebraic setfirst-order theory of real closed fields

Mathematics Subject Classification ID

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

Recommendations

• Finding connected components of a semialgebraic set in subexponential time
• Some speed-ups and speed limits for real algebraic geometry
• scientific article; zbMATH DE number 21309
• scientific article; zbMATH DE number 8550
• scientific article; zbMATH DE number 27176

Cited in

(9)

• \(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
• Complexity of deciding connectivity in real algebraic sets
• Finding irreducible components of some real transcendental varieties
• scientific article; zbMATH DE number 21309 (Why is no real title available?)
• Finding connected components of a semialgebraic set in subexponential time
• Polynomial-time computable approximation of families of semialgebraic sets and combinatorial complexity
• Some speed-ups and speed limits for real algebraic geometry
• Description of the connected components of a semialgebraic set in single exponential time

This page was built for publication: Determination of the 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 Q3364033)