Abstract
For any ℓ>0, we present an algorithm which takes as input a semi-algebraic set, S, defined by P 1≤0,…,P s ≤0, where each P i ∈R[X 1,…,X k ] has degree≤2, and computes the top ℓ Betti numbers of S, b k−1(S),…,b k−ℓ(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 ℓ, 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 nontrivial topological invariants of semialgebraic sets in Rk 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 ℓ=k, an algorithm for computing all the Betti numbers of S whose complexity is \(k^{2^{O(S)}}\) .
Similar content being viewed by others
References
A. A. Agrachev, Topology of quadratic maps and Hessians of smooth maps, in Algebra, Topology, Geometry, Vol. 26 (Russian), pp. 85–124, 162. Itogi Nauki i Tekhniki, Akad. Nauk SSSR, Vsesoyuz. Inst. Nauchn. i Tekhn. Inform., Moscow, 1988. Translated in J. Soviet Math. 49(3) (1990), 990–1013.
A. I. Barvinok, Feasability testing for systems of real quadratic equations, Discrete Comput. Geom. 10 (1993), 1–13.
S. Basu, Computing the first few Betti numbers of semialgebraic sets in single exponential time, J. Symbolic Comput. 41 (2006), 1125–1154.
S. Basu, On bounding the Betti numbers and computing the Euler characteristics of semialgebraic sets, Discrete Comput. Geom. 22 (1999), 1–18.
S. Basu, On different bounds on different Betti numbers, Discrete Comput. Geom. 30 (2003), 65–85.
S. Basu, R. Pollack, and M.-F. Roy, Computing the first Betti number and the connected components of semialgebraic sets, submitted, Found. Comput. Math. Available at [arXiv:math.AG/0603248].
S. Basu, R. Pollack, and M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), 1002–1045.
S. Basu, R. Pollack, and M.-F. Roy, Computing roadmaps of semialgebraic sets on a variety, J. Amer. Math. Soc. 3(1) (1999), 55–82.
S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, 2nd ed., Springer-Verlag, New York, 2006.
L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-Verlag, New York, 1997.
J. Bochnak, M. Coste, and M.-F. Roy, Géométrie algébrique réelle, Springer-Verlag, New York, 1987. Real Algebraic Geometry, Springer-Verlag, New York, 1998.
G. E. Bredon, Sheaf Theory, Springer-Verlag, New York, 1996.
P. Burgisser and F. Cucker, Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets, Journal of Complexity 22(2) (2006), 147–191.
J. Canny, Computing road maps in general semialgebraic sets, Comput. J. 36 (1993), 504–514.
A. Gabrielov and N. Vorobjov, Betti numbers for quantifier-free formulae, Discrete Comput. Geom. 33 (2005), 395–401.
L. Gournay and J. J. Risler, Construction of roadmaps of semialgebraic sets, Appl. Algebra Engrg. Comm. Comput. 4(4) (1993), 239–252.
D. Grigor’ev and D. V. Pasechnik, Polynomial time computing over quadratic maps I. Sampling in real algberaic sets, Comput. Complexity 14 (2005), 20–52.
D. Grigor’ev and N. Vorobjov, Counting connected components of a semialgebraic set in subexponential time, Comput. Complexity 2 (1992), 133–186.
R. M. Hardt, Semialgebraic local triviality in semialgebraic mappings, Amer. J. Math. 102 (1980), 291–302.
J. Heintz, M.-F. Roy, and P. Solernò, Description of the connected components of a semialgebraic set in single exponential time, Discrete Comput. Geom. 11 (1994), 121–140.
J. McCleary, A User’s Guide to Spectral Sequences, 2nd ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2001.
J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280.
O. A. Oleĭnik, Estimates of the Betti numbers of real algebraic hypersurfaces, Mat. Sb. (N.S.) 28(70) (1951), 635–640 (Russian).
O. A. Oleĭnik and I. B. Petrovskii, On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13 (1949), 389–402.
C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.
J. Reif, Complexity of the mover’s problem and generalizations, in Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 421–427, 1979.
J. Renegar, On the computational complexity and geometry of the first-order theory of the reals, J. Symbolic Comput. 13 (1992), 255–352.
E. H. Spanier, Algebraic Topology, McGraw-Hill, New York, 1966.
R. Thom, Sur l’homologie des variétés algébriques réelles, in Differential and Combinatorial Topology, pp. 255–265, Princeton University Press, Princeton, NJ, 1965.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Felipe Cucker.
An erratum to this article can be found at http://dx.doi.org/10.1007/s10208-008-9033-1
Rights and permissions
About this article
Cite this article
Basu, S. Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time. Found Comput Math 8, 45–80 (2008). https://doi.org/10.1007/s10208-005-0208-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10208-005-0208-8