Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials (Q1024388)

Let \(R\) be a real closed field, \(\mathcal P\) a family of \(s\) polynomials of total degree at most \(d\) from \(R[X_1, \ldots, X_k]\), and \(\mathcal Q\) a family of \(m\) polynomials from \(R[X_1, \ldots, X_k, Y_1, \ldots, Y_t]\) with \(\deg_Y Q\leq 2\), \(\deg _X Q\leq d\) for all \(Q\in \mathcal{Q}\). A semi-algebraic set \(S\subset R^{k+t}\) is called \((\mathcal{P} \cup \mathcal{Q})\)-closed if \(S\) is defined by a Boolean formula with atoms of the form \(F=0\), \(F\leq 0\), \(F\geq 0\), \(F\in \mathcal{P} \cup \mathcal{Q}\) connected only by disjunctions and conjunctions. In this paper it is shown that there exists an algorithm that takes as input the description of a \((\mathcal{P} \cup \mathcal{Q})\)-closed semi-algebraic set and computes all its Betti numbers by performing at most \(\bigl( (t+1)(s+1)m+1)(d+1)\bigr)^{2^{O(m+k)}}\) arithmetic operations and comparisons. Such a complexity lies between the doubly exponential time bound for the algorithms available in the general case, and the polynomial complexity in the case of semi-algebraic sets defined by few quadratic inequalities. Moreover, for fixed cardinalities of the defining sets \((\mathcal{P}\) and \( \mathcal{Q})\), the algorithm introduced here has polynomial time complexity in the parameters \(d\), \(t\), \(s\). The algorithm described in the paper under review, too complicated to be sketched here, is an adaptation of \textit{S. Basu}'s work [Found. Comput. Math. 8, No. 1, 45--80 (2008), erratum 81--95 (2008; Zbl 1141.14034)] to the case where there are parameters. The presence of parameters requires a careful analysis of the topology of sets defined by partly quadratic systems of polynomials, analysis which is based on and simplifies a construction introduced by \textit{A. A. Agrachev} [J. Sov. Math. 49, No. 3, 990--1013 (1990; Zbl 0719.58006)].