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

Let R be a real closed field, Q⊂R[Y1,…,Yℓ,X1,…,Xk], with degY(Q)⩽2, degX(Q)⩽d, Q∈Q, #(Q)=m, and P⊂R[X1,…,Xk] with degX(P)⩽d, P∈P, #(P)=s. Let S⊂Rℓ+k be a semi-algebraic set defined by a Boolean formula without negations, with atoms P=0, P⩾0, P⩽0, P∈P∪Q. We describe an algorithm for computing the Betti numbers of S generalizing a similar algorithm described in [S. Basu, Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (1) (2008) 45–80]. The complexity of the algorithm is bounded by ((ℓ+1)(s+1)(m+1)2O(m+k)(d+1)). The complexity of the algorithm interpolates between the doubly exponential time bounds for the known algorithms in the general case, and the polynomial complexity in case of semi-algebraic sets defined by few quadratic inequalities [S. Basu, Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (1) (2008) 45–80]. Moreover, for fixed m and k this algorithm has polynomial time complexity in the remaining parameters.