Compressed decision problems in hyperbolic groups

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 simultaneo...

Full description

Saved in:
Bibliographic Details
Published in:Groups, geometry and dynamics geometry and dynamics, 2024-07, Vol.18 (4), p.1233-1273
Main Authors: Holt, Derek, Lohrey, Markus, Schleimer, Saul
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1661-7207
1661-7215
DOI:10.4171/ggd/809