Derek Holt, Markus Lohrey, Saul Schleimer
Published 2018-08-21Version 1
We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements are input as words defined by straight line programs defined over a finite generating set for the group. We prove also that, for any infinite hyperbolic group $G$, the compressed knapsack problem in $G$ is ${\mathsf{NP}}$-complete.
How many tuples of group elements have a given property?
The conjugacy problem in hyperbolic groups for finite lists of group elements
Formations of Finite Groups in Polynomial Time: $\mathfrak{F}$-residuals and $\mathfrak{F}$-subnormality
![QR code for arXiv:1808.06886 [math.GR]](http://oss.arxitics.com/images/favicon.svg)