Computing the first few Betti numbers of semi-algebraic sets in single exponential time

摘要

In this paper we describe an algorithm that takes as input a description of a semi-algebraic set S is contained in R~k, defined by a Boolean formula with atoms of the form P > 0, P < 0, P = 0 for P ∈ P is contained in R[X_1,.....X_k], and outputs the first l + 1 Betti numbers of S, b_0(S),... ,b_l(S). The complexity of the algorithm is (sd)~(k~(o(l))), where s = #(P) and d =max_(p∈P)deg (P), which is singly exponential in k for l any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler-Poincare characteristic, the zeroth and the first Betti numbers.