Computational topology encompasses an enormous body of research. A complete summary of every complexity result would be impossible. But to give you a small taste, let me expand on your example.
In 1911, Max Dehn posed the word problem for finitely presented groups: Given a string over the generator alphabet, does it represent the identity element? One year later, Dehn described an algorithm for the word problem in fundamental groups of orientable surfaces; equivalently, Dehn described how to decide whether a given cycle on a given orientable surface is contractible. Properly implemented, Dehn's algorithm runs in $O(n)$ time. In the same 1912 paper, Dehn opined that “Solving the word problem for all groups may be as impossible as solving all mathematical problems.”
In 1950, Turing proved that the word problem in finitely presented semigroups is undecidable, by reduction from the halting problem (surprise, surprise).
Building on Turing's result, Markov proved in 1951 that every nontrivial property of finitely-presented semigroups is undecidable. A property of groups is nontrivial if some group has the property and some other group does not. Theoretical computer scientists know the similar result about partial functions as "Rice's Theorem".
In 1952, Novikov proved that the word problem in finitely presented groups is undecidable, thereby proving that Dehn's intuition was correct. The same result was independently proved by Boone in 1954 and Britton in 1958.
In 1955, Adyan proved that every nontrivial property of finitely-presented groups is undecidable. The same result was proved independently by Rabin in 1956. (Yes, that Rabin.)
Finally, in 1958, Markov described algorithms to construct 2-dimensional cell complexes and 4-dimensional manifolds with any desired fundamental group, given the group presentation as input. This result immediately implied that a huge number of topological problems are undecidable, including the following:
- Is a given cycle in a given 2-dimensional complex contractible? (This is the word problem.)
- Is a given 2-complex simply connected? ("Is this group trivial?")
- Is a given cycle in a given 4-manifold contractible?
- Is a given 4-manifold contractible?
- Is a given 4-manifold homeomorphic to a particular 4-manifold (constructed by Markov)?
- Is a given 5-manifold homeomorphic to the 5-sphere (or any other fixed 5-manifold you choose)?
- Is a given 6-complex a manifold?
My favorite corollary of these results is more recent and more subtle: It is undecidable whether a given finitely-presented group is the fundamental group of a 3-manifold. Perelman's recent proof of Thurston's geometrization conjecture implies the existence of an algorithm to determine whether a given 3-manifold has a trivial fundamental group. (As @SamNead points out, results of Rubenstein and Casson imply an algorithm that runs in exponential time.) If a given group $G$ is not a 3-manifold group, then $G$ cannot be trivial, because $\pi_1(S^3)$ is trivial. Thus, if you could decide whether $G$ is a 3-manifold group, you could decide whether $G$ is trivial, which is impossible.
