Computing the Euler-Poincare characteristics of sign conditions
Computing various topological invariants of semi-algebraic sets in single exponential time is an active area of research. Several algorithms are known for deciding emptiness, computing the number of connected components of semi-algebraic sets in single exponential time etc. However, an algorithm for computing all the Betti numbers of a given semi-algebraic set in single exponential time is still lacking. In this paper we describe a new, improved algorithm for computing the Euler-Poincare characteristic (which is the alternating sum of the Betti numbers) of the realization of each realizable sign condition of a family of polynomials restricted to a real variety. The complexity of the algorithm is s(k'+1)O(d)(k) + s(k')((k'log(2)(s) + klog(2)(d))d)(O(k)), where s is the number of polynomials, k the number of variables, d a bound on the degrees, and k' the real dimension of the variety. A consequence of our result is that the Euler-Poincare characteristic of any locally closed semi-algebraic set can be computed with the same complexity. The best previously known single exponential time algorithm for computing the Euler-Poincare characteristic of semi-algebraic sets worked only for a more restricted class of closed semi-algebraic sets and had a complexity of (ksd)(O(k)).
euler-poincare characteristic semi-algebraic sets