The compressed conjugacy problem in relatively hyperbolic groups (Q6495843)

The conjugacy problem \(\mathsf{CP}(G)\) for a group \(G\) takes as input two words \(u\), \(v\) over a generating set \(\Sigma\). The problem is solvable if there is an algorithm that can determine for any such input whether \(u\) and \(v\) are conjugate in \(G\). The answer yes or no is returned.NEWLINENEWLINEThe compressed conjugacy problem \(\mathsf{CCP}(G)\) takes as input straight line programs, \(\mathcal{G}_{1}\) and \(\mathcal{G}_{2}\), which define compressed versions of words \(u\) and \(v\), and asks whether the group elements represented by those values are conjugate in \(G\). In the case when the answer is positive, a solution to the problem would normally be expected to compute a conjugator \(g\), which would be returned as an straight line program for a word representing \(g\). Complexity is measured in terms of the sizes of the input straight line programs, which can be significantly less than the sizes of their values.NEWLINENEWLINEThe main result of the paper under review is Theorem A: The compressed conjugacy problem for a group that is hyperbolic relative to a collection of free abelian subgroups is solvable in polynomial time.