Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time

Details Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time

2006-03-10

arxiv.org/abs/math/0603263v1

Mathematics

Algebraic Geometry

Scientific paper

In this paper we describe an algorithm that takes as input a description of a semi-algebraic set $S \subset \R^k$, defined by a Boolean formula with atoms of the form $P > 0, P < 0, P=0$ for $P \in {\mathcal P} \subset \R[X_1,...,X_k],$ and outputs the first $\ell+1$ Betti numbers of $S$, $b_0(S),...,b_\ell(S).$ The complexity of the algorithm is $(sd)^{k^{O(\ell)}},$ where where $s = #({\mathcal P})$ and $d = \max_{P\in {\mathcal P}}{\rm deg}(P),$ which is singly exponential in $k$ for $\ell$ any fixed constant. Previously, singly exponential time algorithms were known only for computing the Euler-Poincar\'e characteristic, the zero-th and the first Betti numbers.

Affiliated with

Also associated with

No associations

Rating

Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential 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 First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the First Few Betti Numbers of Semi-algebraic Sets in Single Exponential Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-532830