The Isomorphism Problem for Plain Groups Is in ΣP3

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

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 ΣP3. 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).

Original languageEnglish
Title of host publication39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022
EditorsPetra Berenbrink, Benjamin Monmege
Place of PublicationGermany
PublisherSchloss Dagstuhl
Number of pages14
ISBN (Print)9783959772228
DOIs
Publication statusPublished - 1 Mar 2022
EventInternational Symposium on Theoretical Aspects of Computer Science 2022 - Virtual Conference
Duration: 15 Mar 202218 Mar 2022
Conference number: 39th
https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16222 (Proceedings)
https://stacs2022.sciencesconf.org/#:~:text=The%2039th%20International%20Symposium%20on,site%20presence%20component%20in%20Marseille.

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume219
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Theoretical Aspects of Computer Science 2022
Abbreviated titleSTACS 2022
Period15/03/2218/03/22
Internet address

Keywords

  • Inverse-closed finite convergent length-reducing rewriting system
  • Isomorphism problem
  • Plain group
  • Polynomial hierarchy
  • Σ complexity class

Cite this