Computing the first few Betti numbers of semi-algebraic sets in single exponential time

In this paper we describe an algorithm that takes as input a description of a semi-algebraic set , defined by a Boolean formula with atoms of the form P>0,P<0,P=0 for , and outputs the first ℓ+1 Betti numbers of S, b0(S),…,bℓ(S). The complexity of the algorithm is (sd)kO(ℓ), where s=#(P) and d=maxP∈Pdeg(P), which is singly exponential in k for ℓ any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler–Poincaré characteristic, the zeroth and the first Betti numbers.