ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Definition 2.2 (Cylindrical Algebraic Decomposition). <s> Tarski in 1948, (Tarski 1951) published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Definition 2.2 (Cylindrical Algebraic Decomposition). <s> We show that quantifier elimination over real closed fields can require doubly exponential space (and hence time). This is done by explicitly constructing a sequence of expressions whose length is linear in the number of quantifiers, but whose quantifier-free expression has length doubly exponential in the number of quantifiers. The results can be applied to cylindrical algebraic decomposition, showing that this can be doubly exponential. The double exponents of our lower bounds are about one fifth of the double exponents of the best-known upper bounds. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Definition 2.2 (Cylindrical Algebraic Decomposition). <s> Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Definition 2.2 (Cylindrical Algebraic Decomposition). <s> A coordinate cone in R^n is an intersection of some coordinate hyperplanes and open coordinate half-spaces. A semi-monotone set is a defnable in an o-minimal structure over the reals, open bounded subset of R^n such that its intersection with any translation of any coordinate cone is connected. This can be viewed as a generalization of the convexity property. Semi-monotone sets have a number of interesting geometric and combinatorial properties. The main result of the paper is that every semi-monotone set is a topological regular cell. <s> BIB004
A cylindrical algebraic decomposition of R k is a sequence S 1 , . . . , S k where, for each 1 ≤ i ≤ k, S i is a finite partition of R i into semi-algebraic subsets, called the cells of level i, which satisfy the following properties: • Each cell S ∈ S 1 is either a point or an open interval. • For every 1 ≤ i < k and every S ∈ S i , there are finitely many continuous semi-algebraic functions ξ S,1 < . . . < ξ S, S : S −→ R such that the cylinder S × R ⊂ R i+1 is the disjoint union of cells of S i+1 which are: -either the graph of one of the functions ξ S,j , for j = 1, . . . , S : -or a band of the cylinder bounded from below and from above by the graphs of the functions ξ S,j and ξ S,j+1 , for j = 0, . . . , S , where we take ξ S,0 = −∞ and ξ i, S +1 = +∞: Definition 2.3. Given a finite set P ⊂ R[X 1 , . . . , X k ], a subset S of R k is is Pinvariant if every polynomial P ∈ P has a constant sign (> 0, < 0, or = 0) on S. A cylindrical algebraic decomposition of R k adapted to P is a cylindrical algebraic decomposition for which each cell C ∈ S k is P-invariant. It is clear that if S is P-semi-algebraic, a cylindrical algebraic decomposition adapted to P is a cylindrical algebraic decomposition adapted to S. One important result which underlies most algorithmic applications of cylindrical algebraic decomposition is the following (see BIB003 Chapter 11] for an easily accessible exposition). Theorem 2.4. BIB001  For every finite set P of polynomials in R[X 1 , . . . , X k ], there is a cylindrical decomposition of R k adapted to P. Moreover, such a decomposition can be computed in time (sd) , where s = card P and d = max P ∈P deg(P ). Cylindrical algebraic decomposition provides an alternative (and more efficient compared to Tarski's) algorithm for quantifier elimination, since (using the same notation as in the previous section) the semi-algebraic subset of R defined by Φ(Y ), is a union of cells (of various dimensions) in a cylindrical algebraic decomposition of R k+ adapted to P (cf. Definition 2. 3), where Y 1 , . . . , Y are the last variables. This last fact is a consequence of the "cylindrical" structure of the decomposition. The complexity of such an algorithm is bounded by the complexity of computing the cylindrical decomposition and is doubly exponential. More precisely, the complexity is bounded by (sd) Remark 2.5. The technique of cylindrical algebraic decomposition is also used in algorithms for computing topological properties of semi-algebraic sets. After making a generic linear change of co-ordinates, the cylindrical algebraic decomposition algorithm yields a finite cell complex from which topological invariants of the underlying semi-algebraic sets can be extracted. It should be noted that a change of co-ordinates is needed to obtain a cell complex. However, in certain applications a change of co-ordinates is not allowed (see BIB004 for one such application). It is an interesting open question if there always exists a semi-algebraic cell decomposition adapted to a given finite family of polynomials, having a cylindrical structure with respect to the given co-ordinates. 2.1.3. Lower bound. Given the doubly exponential upper bound on the complexity of quantifier elimination algorithm that follows from cylindrical algebraic decomposition, it is interesting to ask whether it is at all possible to do better. This question was investigated by Davenport and Heintz BIB002 who proved a doubly exponential lower bound on the complexity of real quantifier elimination, by constructing a sequence of quantified formula having the property that any equivalent sequence of quantifier-free formulas would necessarily have doubly exponential growth in size. However, the quantified formulas in the sequence they constructed had a large number of quantifier alternations (linear in the number of variables). Thus, while it is impossible to hope for better than doubly exponential dependence in the number, ω, of quantifier alternations, it might still be possible to obtain algorithms with much better complexity (i.e. singly exponential in the number of variables) if we fix the number of quantifier alternations. This is what we describe next.