ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Clearly, in this case <s> A clear exposition, with exercises, of the basic ideas of algebraic topology. Suitable for a two-semester course at the beginning graduate level, it assumes a knowledge of point set topology and basic algebra. Although categories and functors are introduced early in the text, excessive generality is avoided, and the author explains the geometric or analytic origins of abstract concepts as they are introduced. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Clearly, in this case <s> In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth Betti number, and the Euler–Poincare characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem. <s> BIB002
It is a classical fact (usually referred to as the Nerve Lemma) that Theorem 3.13 (Nerve Lemma). Suppose that the cover C(S) satisfies the Leray property. Then for each i ≥ 0, (See for instance BIB001 for a proof.) Remark 3.14. There are several interesting extensions of Theorem 3.13 (Nerve Lemma). For instance, if the Leray property is weakened to say that each t-ary intersection is (k − t + 1)-connected, then one can conclude that the nerve complex is k-connected. We refer the reader to the article by Björner  for more details. Notice that Theorem 3.13 gives a method for computing the Betti numbers of S using linear algebra from a cover of S by contractible sets for which all non-empty intersections are also contractible, once we are able to test emptiness of the various intersections S α0···αp . Now suppose that each individual member, S α0 , of the cover is contractible, but the various intersections S α0···αp are not necessarily contractible for p ≥ 1. Theorem 3.13 does not hold in this case. However, the following theorem is proved in BIB002 and underlies the singly exponential algorithm for computing the first Betti number of semi-algebraic sets described there. Theorem 3.15. BIB002 Suppose that each individual member, S α0 , of the cover C(S) is contractible. Then, Remark 3.16. Notice that from a cover by contractible sets Theorem 3.15 allows us to compute using linear algebra, b 0 (S) and b 1 (S), once we have identified the non-empty semi-algebraically connected components of the pair-wise and triple-wise intersections of the sets in the cover and their inclusion relationships. 3.2.1. Constructing coverings of closed semi-algebraic sets by closed contractible sets. The parametrized paths obtained in Theorem 3.9 are not necessarily closed or even contractible, but become so after making appropriate modifications. At the same time it is possible to maintain the covering property, namely for any given P-closed semi-algebraic S set, there exists a set of modified parametrized paths, whose union is S. Moreover, these modified sets are closed and contractible. We omit the details of this (technical) construction referring the reader to BIB002 for more detail. Putting together the constructions outlined above we have: There exists an algorithm that given as input a P-closed and bounded semi-algebraic set S, outputs a set of formulas {φ 1 , . . . , φ M } such that is semi-algebraically contractible, and where R is some real closed extension of R. The complexity of the algorithm is bounded by s , where s = card P and d = max P ∈P deg(P ).