Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Computing the homology of basic semialgebraic sets in weak exponential time
Bürgisser P., Cucker F., Lairez P. Journal of the ACM66 (1):1-30,2019.Type:Article
Date Reviewed: Mar 26 2019

A semialgebraic set is a subset of a finite-dimensional Euclidean space defined by a finite list of polynomial equalities and inequalities. These sets can be weird, so it desirable to be able to describe their topological shape, in particular, to describe their homology--that is, their Betti numbers and torsion coefficients.

The good news is that such a description is algorithmically possible. The not so good news is that the best known algorithms require doubly exponential time (of the type exp(exp(n))), which makes them not practical already for reasonably small n. Can we do it faster?

This problem is known to be PSPACE-hard, so most probably we cannot have algorithms faster than exponential time ones, but we can at least hope to get exponential time algorithms--which will make them realistic for much larger n. For some topological characteristics--for example, for computing dimension--exponential time algorithms have indeed been discovered, but whether an exponential time algorithm is possible for homologies is still an open problem. From a practical viewpoint, however, the requirement that the computation time is always bounded by an exponential function may be unnecessarily strong. There are many cases where the worst-case complexity of an algorithm is huge, but works well in practice--since if we ignore areas of exponentially decreasing size, everywhere else the running time is much smaller.

The authors describe such a “weakly exponential” algorithm for computing the homology: with the exception of an area of exponentially decreasing size, this algorithm runs in singly exponential time.

Reviewer:  V. Kreinovich Review #: CR146491 (1906-0250)
Bookmark and Share
  Featured Reviewer  
 
Computational Geometry And Object Modeling (I.3.5 )
 
 
General (F.0 )
 
 
General (I.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Computational Geometry And Object Modeling": Date
Computer image synthesis: shapes
Crow F.  Computer culture: the scientific, intellectual, and social impact of the computer (, New York,611984. Type: Proceedings
Jul 1 1986
Table-driven algorithms for generating space-filling curves
Griffiths J. Computer-Aided Design 17(1): 37-41, 1985. Type: Article
Feb 1 1988
Automatic curve fitting with quadratic B-spline functions and its applications to computer-assisted animation
Yang M., Kim C., Cheng K., Yang C., Liu S. Computer Vision, Graphics, and Image Processing 33(3): 346-362, 1986. Type: Article
Sep 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy