Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time
| dc.creator | Basu, Saugata | |
| dc.date | 2006-03-10 | |
| dc.date | 2007-02-22 | |
| dc.date.accessioned | 2026-07-07T07:47:59Z | |
| dc.date.available | 2026-07-07T07:47:59Z | |
| dc.description | 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)}}$. | |
| dc.description | Some more details added in Sections 6 and 7 | |
| dc.identifier | https://arxiv.org/abs/math/0603262 | |
| dc.identifier | http://arxiv.org/abs/math/0603262 | |
| dc.identifier | doi:10.1007/s10208-005-0208-8 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/124348 | |
| dc.subject | Algebraic Geometry | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic | |
| dc.title | Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time | |
| dc.type | text |