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 ♦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 TowersJun 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).
answered Jun 30, 2016 at 4:46