# Computing the Top Betti Numbers of Semi-algebraic Sets Defined by
Quadratic Inequalities in Polynomial Time

Research paper by **Saugata Basu**

Indexed on: **22 Feb '07**Published on: **22 Feb '07**Published in: **Mathematics - Algebraic Geometry**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

For any $\ell > 0$, we present an algorithm which takes as input a
semi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each
$P_i \in \R[X_1,...,X_k]$ has degree $\leq 2,$ and computes the top $\ell$
Betti numbers of $S$, $b_{k-1}(S), ..., b_{k-\ell}(S),$ in polynomial time. The
complexity of the algorithm, stated more precisely, is $ \sum_{i=0}^{\ell+2} {s
\choose i} k^{2^{O(\min(\ell,s))}}. $ For fixed $\ell$, 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 non-trivial topological invariants of
semi-algebraic 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 $\ell = k$, an
algorithm for computing all the Betti numbers of $S$ whose complexity is
$k^{2^{O(s)}}$.