Geodesic
Compressed decision problems in hyperbolic groups
Derek Holt1 ; Markus Lohrey2 orcid ; Saul Schleimer1 orcid
1University of Warwick, Coventry, UK
2Universität Siegen, Siegen, Germany
Groups, geometry, and dynamics, Tome 18 (2024) no. 4, pp. 1233-1273

Voir la notice de l'article provenant de la source EMS Press

DOI

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 NP-complete.
DOI : 10.4171/ggd/809
Classification : 20F10, 20F67
Mots-clés : algorithmic group theory, hyperbolic groups, word problem, straight-line programs

Derek Holt  1   ; Markus Lohrey  2   ; Saul Schleimer  1

1 University of Warwick, Coventry, UK
2 Universität Siegen, Siegen, Germany 
Derek Holt; Markus Lohrey; Saul Schleimer. Compressed decision problems in hyperbolic groups. Groups, geometry, and dynamics, Tome 18 (2024) no. 4, pp. 1233-1273. doi: 10.4171/ggd/809
@article{10_4171_ggd_809,
     author = {Derek Holt and Markus Lohrey and Saul Schleimer},
     title = {Compressed decision problems in hyperbolic groups},
     journal = {Groups, geometry, and dynamics},
     pages = {1233--1273},
     year = {2024},
     volume = {18},
     number = {4},
     doi = {10.4171/ggd/809},
     url = {http://geodesic.mathdoc.fr/articles/10.4171/ggd/809/}
}
TY  - JOUR
AU  - Derek Holt
AU  - Markus Lohrey
AU  - Saul Schleimer
TI  - Compressed decision problems in hyperbolic groups
JO  - Groups, geometry, and dynamics
PY  - 2024
SP  - 1233
EP  - 1273
VL  - 18
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4171/ggd/809/
DO  - 10.4171/ggd/809
ID  - 10_4171_ggd_809
ER  - 
%0 Journal Article
%A Derek Holt
%A Markus Lohrey
%A Saul Schleimer
%T Compressed decision problems in hyperbolic groups
%J Groups, geometry, and dynamics
%D 2024
%P 1233-1273
%V 18
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4171/ggd/809/
%R 10.4171/ggd/809
%F 10_4171_ggd_809

Cité par Sources :