License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.26
URN: urn:nbn:de:0030-drops-158368
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15836/
Go to the corresponding LIPIcs Volume Portal

Dietrich, Heiko ; Elder, Murray ; Piggott, Adam ; Qiao, Youming ; Weiß, Armin

The Isomorphism Problem for Plain Groups Is in Σ₃^{?}

pdf-format:
LIPIcs-STACS-2022-26.pdf (0.8 MB)

Abstract

Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. Sénizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in PSPACE when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of plain groups, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in Σ₃^?. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemerédi (1984).

BibTeX - Entry

@InProceedings{dietrich_et_al:LIPIcs.STACS.2022.26,
  author =	{Dietrich, Heiko and Elder, Murray and Piggott, Adam and Qiao, Youming and Wei{\ss}, Armin},
  title =	{{The Isomorphism Problem for Plain Groups Is in \Sigma₃^\{?\}}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15836},
  URN =		{urn:nbn:de:0030-drops-158368},
  doi =		{10.4230/LIPIcs.STACS.2022.26},
  annote =	{Keywords: plain group, isomorphism problem, polynomial hierarchy, \Sigma₃^\{?\} complexity class, inverse-closed finite convergent length-reducing rewriting system}
}

Keywords: plain group, isomorphism problem, polynomial hierarchy, Σ₃^{?} complexity class, inverse-closed finite convergent length-reducing rewriting system
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

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