Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time

摘要

For any l>0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P-1 <= 0,...,P-s <= 0, where each P-i is an element of R[X-1,...,X-k] has degree <= 2, and computes the top l Betti numbers of S, b(k-1)(S),...,b(k-l)(S), in polynomial time. The complexity of the algorithm, states more precisely, is (i=0)Sigma(l+2)()(i)(s) k(2o(min(l,s))). For fixed l, the complexity of the algorithm can be expressed as s(l+2)k(2o(l)), which is polynomial in the input parameters s and k. To our knowledge this is the first polynomial time algorithm for computing nontrivial topological invariants of semialgebraic sets in R-k defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed s, we obtain, by letting l=k, an algorithm for computing all the Betti numbers of S whose complexity is k(2o(s)).