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

摘要

Let R be a real closed field, Q R|Y_1,..., Y_k, X_1,...,X_k|, with degy(Q) ≤ 2, degx(Q) ≤ d, Q ∈ Q. #(Q) = m, and P R|X_1,..., X_k| with deg_x(P)≤ d, P ∈ P, #(P) = s. Let S R~(e+k) be a semi-algebraic set defined by a Boolean formula without negations, with atoms P = 0, P≥ 0, P≤O, 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 ((e + 1)(s + 1)(m + 1)(d + 1))2_(m+k) 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-801. Moreover, for fixed m and k this algorithm has polynomial time complexity in the remaining parameters.