Skip to main content
Springer Nature Link
Log in

Computing the Top Betti Numbers of Semialgebraic Sets Defined by Quadratic Inequalities in Polynomial Time

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

An Erratum to this article was published on 01 February 2008

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)}}\) .

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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.

  2. A. I. Barvinok, Feasability testing for systems of real quadratic equations, Discrete Comput. Geom. 10 (1993), 1–13.

    Article  MathSciNet  MATH  Google Scholar 

  3. S. Basu, Computing the first few Betti numbers of semialgebraic sets in single exponential time, J. Symbolic Comput. 41 (2006), 1125–1154.

    Article  MathSciNet  MATH  Google Scholar 

  4. S. Basu, On bounding the Betti numbers and computing the Euler characteristics of semialgebraic sets, Discrete Comput. Geom. 22 (1999), 1–18.

    Article  MathSciNet  MATH  Google Scholar 

  5. S. Basu, On different bounds on different Betti numbers, Discrete Comput. Geom. 30 (2003), 65–85.

    MathSciNet  MATH  Google Scholar 

  6. 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].

  7. S. Basu, R. Pollack, and M.-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM 43 (1996), 1002–1045.

    Article  MathSciNet  MATH  Google Scholar 

  8. 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.

    MathSciNet  Google Scholar 

  9. S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, 2nd ed., Springer-Verlag, New York, 2006.

    MATH  Google Scholar 

  10. L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-Verlag, New York, 1997.

    MATH  Google Scholar 

  11. 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.

    MATH  Google Scholar 

  12. G. E. Bredon, Sheaf Theory, Springer-Verlag, New York, 1996.

    Google Scholar 

  13. P. Burgisser and F. Cucker, Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets, Journal of Complexity 22(2) (2006), 147–191.

    Article  MathSciNet  Google Scholar 

  14. J. Canny, Computing road maps in general semialgebraic sets, Comput. J. 36 (1993), 504–514.

    Article  MathSciNet  MATH  Google Scholar 

  15. A. Gabrielov and N. Vorobjov, Betti numbers for quantifier-free formulae, Discrete Comput. Geom. 33 (2005), 395–401.

    Article  MathSciNet  MATH  Google Scholar 

  16. L. Gournay and J. J. Risler, Construction of roadmaps of semialgebraic sets, Appl. Algebra Engrg. Comm. Comput. 4(4) (1993), 239–252.

    Article  MathSciNet  MATH  Google Scholar 

  17. 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.

    Article  MathSciNet  Google Scholar 

  18. D. Grigor’ev and N. Vorobjov, Counting connected components of a semialgebraic set in subexponential time, Comput. Complexity 2 (1992), 133–186.

    Article  MathSciNet  MATH  Google Scholar 

  19. R. M. Hardt, Semialgebraic local triviality in semialgebraic mappings, Amer. J. Math. 102 (1980), 291–302.

    Article  MathSciNet  MATH  Google Scholar 

  20. 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.

    Article  MathSciNet  MATH  Google Scholar 

  21. J. McCleary, A User’s Guide to Spectral Sequences, 2nd ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2001.

    MATH  Google Scholar 

  22. J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280.

    Article  MathSciNet  MATH  Google Scholar 

  23. O. A. Oleĭnik, Estimates of the Betti numbers of real algebraic hypersurfaces, Mat. Sb. (N.S.) 28(70) (1951), 635–640 (Russian).

    Google Scholar 

  24. O. A. Oleĭnik and I. B. Petrovskii, On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13 (1949), 389–402.

    Google Scholar 

  25. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.

    MATH  Google Scholar 

  26. J. Reif, Complexity of the mover’s problem and generalizations, in Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 421–427, 1979.

  27. J. Renegar, On the computational complexity and geometry of the first-order theory of the reals, J. Symbolic Comput. 13 (1992), 255–352.

    Article  MathSciNet  MATH  Google Scholar 

  28. E. H. Spanier, Algebraic Topology, McGraw-Hill, New York, 1966.

    MATH  Google Scholar 

  29. 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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA

    Saugata Basu

Authors
  1. Saugata Basu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saugata Basu.

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

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-005-0208-8

Keywords

AMS Subject Classifications

Search

Navigation