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

DOI10.4230/LIPICS.CCC.2020.29MaRDI QIDQ6326261arXivFDO

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

Publication date 30 September 2019

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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.

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)