A semialgebraic set is a subset of a finite-dimensional Euclidean space defined by a finite list of polynomial equalities and inequalities. These sets can be weird, so it desirable to be able to describe their topological shape, in particular, to describe their homology--that is, their Betti numbers and torsion coefficients.

The good news is that such a description is algorithmically possible. The not so good news is that the best known algorithms require doubly exponential time (of the type exp(exp(n))), which makes them not practical already for reasonably small n. Can we do it faster?

This problem is known to be PSPACE-hard, so most probably we cannot have algorithms faster than exponential time ones, but we can at least hope to get exponential time algorithms--which will make them realistic for much larger n. For some topological characteristics--for example, for computing dimension--exponential time algorithms have indeed been discovered, but whether an exponential time algorithm is possible for homologies is still an open problem. From a practical viewpoint, however, the requirement that the computation time is always bounded by an exponential function may be unnecessarily strong. There are many cases where the worst-case complexity of an algorithm is huge, but works well in practice--since if we ignore areas of exponentially decreasing size, everywhere else the running time is much smaller.

The authors describe such a “weakly exponential” algorithm for computing the homology: with the exception of an area of exponentially decreasing size, this algorithm runs in singly exponential time.