Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time

摘要

For any ?>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 ∈R[X 1,…,X k ] has degree≤2, and computes the top ? Betti numbers of S, b k?1(S),…,b k?? (S), in polynomial time. The complexity of the algorithm, stated more precisely, is $sum_{i=0}^{ell+2}{schoose i}k^{2^{o(min(ell,s))}}$ . For fixed ?, the complexity of the algorithm can be expressed as $s^{ell+2}+k^{2^{O(ell)}}$ , 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 ?=k, an algorithm for computing all the Betti numbers of S whose complexity is $k^{2^{O(S)}}$ .