Compressed decision problems in hyperbolic groups (Q6619327)

Let \(G\) be a finitely generated group and \(\Sigma\) a finite symmetric generating set of \(G\). The word problem for \(G\) asks, given a word \(w \in \Sigma^{\ast}\) if \(w\) represents the identity in \(G\). The compressed word problem for \(G\) finitely is the word problem in the usual sense, with the difference that the input word is compressed as a straight-line program. The compressed word problem for \(G\) is decidable if and only if the word problem for \(G\) is decidable but, since computational complexity is measured relative to the input size, the computational complexity of the compressed word problem for \(G\) can be strictly more difficult than the word problem itself.\N\NA word \(w\) in the generators of \(G\) is shortlex reduced if it is shorter than or equal to the same length and lexicographically earlier than, any other word representing the same group element.\N\NLet \(\mathcal{G}\) be a straight-line program over \(\Sigma\) and let \(\mathsf{eval}(\mathcal{G})\) be the output of \(\mathcal{G}\). The main result in the paper under review is Theorem 5.7: Let \(G\) be a hyperbolic group, with symmetric generating set \(\Sigma\). There is a polynomial-time algorithm that, given a straight-line program \(\mathcal{G}\) over \(\Sigma\), finds a straight-line program \(\mathcal{H}\) so that \(\mathsf{eval}(\mathcal{H})\) is the shortlex reduction of \(\mathsf{eval}(\mathcal{G})\).\N\NFrom this theorem, the authors deduce the important Corollary 5.8: Let \(G\) be a hyperbolic group. Then the compressed word problem for \(G\) can be solved in polynomial time.\N\NIf in the conjugacy problem the given pair of elements is replaced by a pair of finite ordered lists of elements, then one obtains the simultaneous conjugacy problem. In the centraliser problem, the input consists of a list of group elements \(g_{1}, \ldots, g_{k} \in G\) and the goal is to compute a set of generators for the intersection of the centralisers of the \(g_{i}\). Thanks to the previous results, the authors prove that the compressed simultaneous conjugacy problem and the compressed centraliser problem for hyperbolic groups can be solved in polynomial time. Furthermore, they prove that the compressed knapsack problem for hyperbolic groups is \(\mathsf{NP}\)-complete.