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

For a semi-algebraic set \(S\subset\mathbb{R}^k\) defined by a Boolean formula with atoms of the form \(P>0\), \(P<0\), \(P=0\), for \(P\in\mathcal{P}\subset\mathcal{R}[X_1,\dots,X_k]\), an algorithm is described that outputs the first \(\ell+1\) Betti numbers of \(S\). The complexity of the algorithm is \((sd)^{k^{O(\ell)}}\), for \(s=| \mathcal{P}| \), and \(d\) a bound on the degrees of \(P\in\mathcal{P}\). That is, the complexity is single exponential in \(k\). Previously, algorithms with such a complexity bound were only known for the cases \(\ell=0\) and \(\ell=1\) (and for computing the Euler-Poincaré characteristic of \(S\)), cf. e.g. [\textit{S. Basu, R. Pollack} and \textit{M.-F. Roy}, Algorithms in real algebraic geometry. Berlin: Springer (2006; Zbl 1102.14041)]. For the remaining cases, only procedures with doubly exponential complexity in \(k\), that is, with complexity \((sd)^{2^{O(k)}}\), were known. The author had to overcome the absence of natural geometric objects, that is typical when higher homology groups are considered, by using involved algebraic topology machinery.