10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I added the [reference-request] tag. $\endgroup$ – David Roberts Jun 30 '16 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 Jun 30 '16 at 5:56
13
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.