Computing the homology of semialgebraic sets. II: General formulas (Q2052718)

The authors exhibit a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. This work extends to arbitrary semialgebraic sets the results in part I [\textit{P. Bürgisser} et al., Found. Comput. Math. 20, No. 1, 71--118 (2020; Zbl 1440.14264)]. Complements are allowed in the Boolean combinations (or, equivalently, negations in the Boolean formulas) describing semialgebraic sets and so are strict inequalities. The new algorithm works in weak exponential time. This means that its cost, or running time, is single exponential outside an exceptional set whose measure vanishes exponentially fast. Outside this exceptional set then, the algorithm works exponentially faster than state-of-the-art algorithms (which are doubly exponential).