Mathematics – Algebraic Geometry
Scientific paper
2006-03-10
Mathematics
Algebraic Geometry
Some more details added in Sections 6 and 7
Scientific paper
10.1007/s10208-005-0208-8
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)}}$.
Basu Saugata
No associations
LandOfFree
Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the Top Betti Numbers of Semi-algebraic Sets Defined by Quadratic Inequalities in Polynomial Time will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-532827