Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

DOI10.4230/LIPICS.CCC.2020.29arXiv1909.13781MaRDI QIDQ6326261FDOQ6326261

Authors: Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß 

Publication date: 30 September 2019

Abstract: We give lower bounds on the complexity of the word problem of certain non-solvable groups: for a large class of non-solvable infinite groups, including in particular free groups, Grigorchuk's group and Thompson's groups, we prove that their word problem is $mathsf{NC}^1$-hard. For some of these groups (including Grigorchuk's group and Thompson's groups) we prove that the compressed word problem (which is equivalent to the circuit evaluation problem) is $mathsfPSPACE$-complete.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

This page was built for publication: Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326261)