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

zbMATH Open0801.68098MaRDI QIDQ3364033FDOQ3364033

Authors: Nicolai Vorobjov, Dima Grigoriev 

Publication date: 1991

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

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)

Cited In (9)

• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• \(N\)-dimensional versus \((N-1)\)-dimensional connectivity testing of first-order queries to semi-algebraic sets
• Complexity of deciding connectivity in real algebraic sets
• Finding irreducible components of some real transcendental varieties
• Title not available (Why is that?)
• 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)