Quantifying complexity for the isomorphism problem of hyperbolic groups

Abstract:

Deciding whether two finite presentations represent isomorphic groups is very hard. By a classical result of Adyan and Rabin, the problem of deciding whether a given presentation gives the trivial group is undecidable, so the isomorphism problem is undecitable in general. However, for certain classes of groups the isomorphism problem has been shown to be solvable. In the case of hyperbolic groups, an algorithm deciding the isomorphism problem was given by Dahmani and Guirardel. Unfortunately, this algorithm is not primitively recursive, meaning that there is no bound on its complexity. In my talk I will show that if we restrict our attention only to rigid hyperbolic groups, then one can actually give an upper bound on the complexity, provided that we are given an additional piece of information (the rigidity constant). The class of rigid hyperbolic groups includes fundamental groups of closed compact hyperbolic 3-manifolds, so by Mostow rigidity we get an upper bound on the complexity of homeomorphism problem for closed compact hyperbolic 3-manifolds as well.