Is there any literature regarding the fastest known algorithm to compute the homology groups of a simplicial complex (on n vertices)? What about computing the fundamental group? The context is to tell whether a given simplical complex is contractible by showing that the fundamental group and all reduced homology groups vanish, but if there is a faster way to compute whether a simplicial complex is contractible then that would be helpful as well.
$\begingroup$ $\endgroup$
2 
- $\begingroup$ I added the [reference-request] tag. $\endgroup$David Roberts– David Roberts ♦2016-06-30 04:37:37 +00:00Commented Jun 30, 2016 at 4:37
- 3$\begingroup$ Note that your context includes the undecidable problem of determining in general whether a group is trivial given a (finite) presentation of it. (This is a particular case of the group isomorphism problem that is also known to be undecidable.) $\endgroup$Eric Towers– Eric Towers2016-06-30 05:56:52 +00:00Commented Jun 30, 2016 at 5:56
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
Homology groups can be computed with Smith normal form (see this survey). As for deciding if a simplicial complex is contractible, that is difficult. It is undecidable to tell if a simplicial complex is contractible (see appendix A of this paper). The same paper shows that it is NP-hard to decide if a simplicial complex is collapsible (a condition which implies contractible).
