Compressed decision problems in hyperbolic groups
Derek Holt
University of Warwick, Coventry, UKMarkus Lohrey
Universität Siegen, Siegen, GermanySaul Schleimer
University of Warwick, Coventry, UK
![Compressed decision problems in hyperbolic groups cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserials%2Fcover-ggd.png&w=3840&q=90)
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 -complete.
Cite this article
Derek Holt, Markus Lohrey, Saul Schleimer, Compressed decision problems in hyperbolic groups. Groups Geom. Dyn. (2024), published online first
DOI 10.4171/GGD/809