摘要
Let be a real closed field and an ordered domain. We present an algorithm that takes as input a polynomial and computes a description of a roadmap of the set of zeros, of Q in The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain is bounded by where As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, whose complexity is also bounded by where The best previously known algorithm for constructing a roadmap of a real algebraic subset of defined by a polynomial of degree d has complexity.
- 出版日期2014-12