On projections of semi-algebraic sets defined by few quadratic inequalities

摘要

Let S subset of Rk+m be a compact semi-algebraic set defined by P-1 >= 0, ..., P-l >= 0, where P-i is an element of R[X-1, ..., X-k, Y-1, ..., Y-m], and deg(P-i) <= 2, 1 <= i <= l. Let p denote the standard projection from Rk+m onto R-m. We prove that for any q > 0, the sum of the first q Betti numbers of pi(S) is bounded by (k+ m)(O(ql)). We also present an algorithm for computing the first q Betti numbers of pi(S), whose complexity is (k + m)(2O(ql)). For fixed q and l, both the bounds are polynomial in k + m.