ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Computing topological invariants of semi-algebraic sets <s> PROOF. Approximate fi, * *, fm by real polynomials F1, * , Fm of the same degrees whose coefficients are algebraically independent. Now consider the variety Vc in the complex Cartesian space C'defined by the equations F1 =0, * * *, Fm =0. It follows from van der Waerden [9, ?41 ] that the number of points in Vc is equal to (deg fi) (deg f2) . . (deg fm). Since each point of V0 lies close to some real point of Vc; this proves Lemma 1. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Computing topological invariants of semi-algebraic sets <s> Abstract. In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S ::: $\subset$ Rk defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form Pi=0, Pi≥ 0, Pi≤ 0, deg(Pi) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by sk'(O(d))k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by sk' 2O(k2 m4) in case the total number of monomials occurring in the polynomials in ::: $ {\cal P} \cup \{Q\}$ is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Computing topological invariants of semi-algebraic sets <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> Computing topological invariants of semi-algebraic sets <s> Let X be a semialgebraic set in Rn defined by a Boolean combination of atomic formulae of the kind h * 0 where * \in { >, \ge, = }, deg(h) < d, and the number of distinct polynomials h is k. We prove that the sum of Betti numbers of X is less than O(k2d)n. <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Computing topological invariants of semi-algebraic sets <s> Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form fi>0, 0,1 ≦ i ≦ where the polynomials fieℤ[X1,..., Xn] of degree deg (fi)<d have absolute value of the coefficients at most 2M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd)ro(1). Collins' previously known method has a bound which is polynomial inM (kd)ro(1). <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Computing topological invariants of semi-algebraic sets <s> We prove new upper bounds on homotopy and homology groups of o-minimal sets in terms of ::: their approximations by compact o-minimal sets. In particular, we improve the known upper ::: bounds on Betti numbers of semialgebraic sets defined by quantifier-free formulae and obtain, ::: for the first time, a singly exponential bound on Betti numbers of sub-Pfaffian sets. <s> BIB006
As remarked above (see Remark 2.23), an effective algorithm for deciding connectivity of semi-algebraic sets does not automatically follow from the TarskiSeidenberg principle. However, one can decide questions about connectivity (as well as compute other topological invariants such as the Betti numbers) using effective triangulation of semi-algebraic sets via Cylindrical Algebraic Decomposition. However, such an algorithm will necessarily have doubly exponential complexity. Most of the recent work in algorithmic semi-algebraic geometry has focused on obtaining singly exponential time algorithms -that is algorithms with complexity of the order of (sd) k . An important motivating reason behind the search for such algorithms, is the following theorem due to Gabrielov and Vorobjov BIB006 (see also BIB004 ) (see   BIB001 BIB002 , as well as the survey article  , for work leading up to this result) which gives singly exponential upper bound on the topological complexity of semi-algebraic sets measured by the sum of their Betti numbers. Theorem 3.1. [43] For a P-semi-algebraic set S ⊂ R k , the sum of the Betti numbers of S is bounded by (O(skd) ) k , where s = card P, and d = max P ∈P deg(P ). For the special case of P-closed semi-algebraic sets the following slightly better bound was known before BIB002 (and this bound is used in an essential way in the proof of Theorem 3.1). Using the same notation as in Theorem 3.1 above we have Theorem 3.2. [7] For a P-closed semi-algebraic set S ⊂ R k , the sum of the Betti numbers of S is bounded by (O(sd)) k . Remark 3.3. These bounds are asymptotically tight, as can be already seen from the example where each P ∈ P is a product of d generic polynomials of degree one. The number of semi-algebraically connected components of the P-semi-algebraic set defined as the subset of R k where all polynomials in P are non-zero is clearly bounded from below by (Csd) k for some constant C. 3.1. Roadmaps. Theorem 2.15 gives a singly exponential time algorithm for testing if a given semi-algebraic set is empty or not. However, it gives no way of testing if any two sample points computed by it belong to the same semi-algebraically connected component of the given semi-algebraic set, even though the set of sample points is guaranteed to meet each such semi-algebraically connected component. In order to obtain connectivity information in singly exponential time a more sophisticated construction is required -namely that of a roadmap of a semi-algebraic set, which is an one dimensional semi-algebraic subset of the given semi-algebraic set which is non-empty and semi-algebraically connected inside each semi-algebraically connected component of the given set. Roadmaps were first introduced by Canny  , but similar constructions were considered as well by Grigoriev and Vorobjov BIB005 and Gournay and Risler  . Our exposition below follows that in  BIB003 where the most efficient algorithm for computing roadmaps is given. The notions of pseudo-critical points and values defined above play a critical role in the design of efficient algorithms for computing roadmaps of semi-algebraic sets. We first define a roadmap of a semi-algebraic set. We use the following notation. We denote by π 1...j the projection, x → (x 1 , . . . , x j ). Given a set S ⊂ R k and y ∈ R j , we denote by S y = S ∩ π −1 1...j (y). Definition 3.4 (Roadmap of a semi-algebraic set). Let S ⊂ R k be a semi-algebraic set. A roadmap for S is a semi-algebraic set M of dimension at most one contained in S which satisfies the following roadmap conditions: • RM 1 For every semi-algebraically connected component D of S, D ∩ M is non-empty and semi-algebraically connected. • RM 2 For every x ∈ R and for every semi-algebraically connected component We describe the construction of a roadmap RM(Z(Q, R k ), N ) for a bounded algebraic set Z(Q, R k ) which contains a finite set of points N of Z(Q, R k ). A precise description of how the construction can be performed algorithmically can be found in BIB003 . We should emphasize here that RM(Z(Q, R k ), N ) denotes the semi-algebraic set output by the specific algorithm described below which satisfies the properties stated in Definition 3.4 (cf. Proposition 3.5). Also, in order to understand the roadmap algorithm it is easier to first concentrate on the case of a bounded and non-singular real algebraic set in R k (see Figure  3 below ). In this case several definitions get simplified. For example, the pseudocritical values defined below are in this case ordinary critical values of the projection map on the first co-ordinate. However, one should keep in mind that even if one starts with a bounded non-singular algebraic set, the input to the recursive calls corresponding to the critical sections (see below) are necessarily singular and thus it is not possible to treat the non-singular case independently. A key ingredient of the roadmap is the construction of pseudo-critical points and values defined above. The construction of the roadmap of an algebraic set containing a finite number of input points N of this algebraic set is as follows. We first construct X 2 -pseudo-critical points on Z(Q, R k ) in a parametric way along the X 1 -axis by following continuously, as x varies on the X 1 -axis, the X 2 -pseudocritical points on Z(Q, R k ) x . This results in curve segments and their endpoints on Z(Q, R k ). The curve segments are continuous semi-algebraic curves parametrized by open intervals on the X 1 -axis and their endpoints are points of Z(Q, R k ) above the corresponding endpoints of the open intervals. Since these curves and their endpoints include for every x ∈ R the X 2 -pseudo-critical points of Z(Q, R k ) x , they meet every semi-algebraically connected component of Z(Q, R k ) x . Thus, the set of curve segments and their endpoints already satisfy RM 2 . However, it is clear that this set might not be semi-algebraically connected in a semi-algebraically connected component and so RM 1 might not be satisfied. We add additional curve segments to ensure connectedness by recursing in certain distinguished hyper-planes defined by X 1 = z for distinguished values z. The set of distinguished values is the union of the X 1 -pseudo-critical values, the first coordinates of the input points N , and the first coordinates of the endpoints of the curve segments. A distinguished hyper-plane is an hyper-plane defined by X 1 = v, where v is a distinguished value. The input points, the endpoints of the curve segments, and the intersections of the curve segments with the distinguished hyper-planes define the set of distinguished points. Let the distinguished values be v 1 < . . . < v . Note that amongst these are the X 1 -pseudo-critical values. Above each interval (v i , v i+1 ) we have constructed a collection of curve segments C i meeting every semi-algebraically connected component of Z(Q, R k ) v for every v ∈ (v i , v i+1 ). Above each distinguished value v i we have a set of distinguished points N i . Each curve segment in C i has an endpoint in N i and another in N i+1 . Moreover, the union of the N i contains N . We then repeat this construction in each distinguished hyper-plane H i defined by X 1 = v i with input Q(v i , X 2 , . . . , X k ) and the distinguished points in N i . Thus, we construct distinguished values v i,1 , . . . , v i, (i) of Z(Q(v i , X 2 , . . . , X k ), R k−1 ) (with the role of X 1 being now played by X 2 ) and the process is iterated until for The following theorem is proved in  (see also BIB003 ). Proposition 3.5. The semi-algebraic set RM(Z(Q, R k ), N ) obtained by this construction is a roadmap for Z(Q, R k ) containing N . 3.1.1. Roadmaps of general semi-algebraic sets. Using the same ideas as above and some additional techniques for controlling the combinatorial complexity of the algorithm it is possible to extend the roadmap algorithm to the case of semi-algebraic sets. The following theorem appears in  BIB003 . of dimension k and let P ⊂ R[X 1 , . . . , X k ] be a set of at most s polynomials for which the degrees of the polynomials in P and Q are bounded by d. Let S be a P-semi-algebraic subset of Z(Q, R k ). There is an algorithm which computes a roadmap RM(S) for S with Theorem 3.6 immediately implies that there is an algorithm whose output is exactly one point in every semi-algebraically connected component of S and whose complexity in the ring generated by the coefficients of Q and P is bounded by . In particular, this algorithm counts the number semi-algebraically connected component of S within the same time bound. . Complex algebraic techniques related to the geometry of polar varieties play an important role in this algorithm. More recently, a deterministic algorithm for computing roadmaps of arbitrary real algebraic sets with the same complexity bound, has also been obtained  . This algorithm is based on techniques coming from semi-algebraic geometry and can be seen as a direct generalization of Proposition 3.5 above. The main new idea is to consider the critical points of projection maps onto a co-ordinate subspace of dimension bigger than 1 (in fact, of dimension √ k). As a result the dimensions in the recursive calls to the algorithm decreases by √ k at each step of the recursion (compared to the case of the ordinary roadmap algorithms where it decreases by 1 in each step). This results in the improved complexity. One also needs to prove suitable generalizations of the results guaranteeing the connectivity of the roadmap (see BIB003 Chapter 15] ) in this more general situation.