Computing the homology of semialgebraic sets. I: Lax formulas (Q2291730)

In the article, the authors present an algorithm for computing the Betti numbers and torsion coefficients of closed semialgebraic sets. Semialgebraic sets are subsets of \(\mathbb{R}^n\) defined by Boolean combinations (i.e., a sequence of unions, intersections, and complements) of polynomial equalities and inequalities. The class of these sets is closed under unions, intersections, complements, and projections as well as under taking images and preimages of polynomial maps. Semialgebraic sets play a distinguished role in several branches of mathematics including real algebraic geometry, complexity theory, mathematical programming, robotics, etc. In this article, the authors focus on semialgebraic sets given by Boolean formulas without negations over lax polynomial inequalities i.e., they are defined by only unions and intersections of the atomic sets. In contrast to the doubly exponential complexity of previous algorithms for computing the sequence of homology groups of semialgebraic sets, the algorithm proposed in this article works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data.