Compressed decision problems in hyperbolic groups

Abstract

We prove that, for any hyperbolic group, the compressed word and the compressed conjugacy problems are solvable in polynomial time. As a consequence, the word problem for the (outer) automorphism group of a hyperbolic group is solvable in polynomial time. We also prove that the compressed simultaneous conjugacy and the compressed centraliser problems are solvable in polynomial time. Finally, we prove that, for any infinite hyperbolic group, the compressed knapsack problem is $\mathrm{NP}$-complete.