2026-07-28T19:07:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10276 2024-03-06T10:45:41Z ddc:004 open_access

Compressed Decision Problems in Hyperbolic Groups Holt, Derek Lohrey, Markus Schleimer, Saul hyperbolic groups algorithms for compressed words circuit evaluation problems 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 NP-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Derek Holt and Markus Lohrey and Saul Schleimer 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.37 urn:nbn:de:0030-drops-102766 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.37 eng https://creativecommons.org/licenses/by/3.0/legalcode