Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Holt, Derek; Lohrey, Markus; Schleimer, Saul https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-102766
URL:

; ;

Compressed Decision Problems in Hyperbolic Groups

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{holt_et_al:LIPIcs:2019:10276,
  author =	{Derek Holt and Markus Lohrey and Saul Schleimer},
  title =	{{Compressed Decision Problems in Hyperbolic Groups}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10276},
  doi =		{10.4230/LIPIcs.STACS.2019.37},
  annote =	{Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems}
}

Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems
Seminar: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue date: 2019
Date of publication: 12.03.2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI