###
Conjugacy of finite subsets in hyperbolic groups

#### Martin R. Bridson and James Howie

#### Preprint, October 2003 --- submitted for publication.

We prove that there exists a quadratic-time algorithm that determines
conjugacy between finite subsets in any torsion-free
hyperbolic group. Moreover, in any $k$-generator,
$\delta$-hyperbolic group $\G$, if two finite subsets $A$
and $B$ are conjugate, then $x^{-1}Ax=B$ for
some $x\in\G$ with $\|x\|$ less than a linear function of
$\max\{\|\g\| : \g\in A\cup B\}$. (The coefficients of this
linear function depend only on $k$ and $\delta$.)

These results have implications for group-based cryptography
and the width of homotopies in negatively curved spaces.

In an appendix, we construct examples of finitely presented
groups in which the conjugacy problem for individual elements
is soluble but the conjugacy problem for finite subsets is not.