Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems
Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß · ACM Transactions on Computation Theory · 2022
We give lower bounds on the complexity of the word problem for a large class of non-solvable infinite groups that we call strongly efficiently non-solvable groups. This class includes free groups, Grigorchuk’s group, and Thompson’s groups. We prove that these groups have an NC 1 -hard word problem and that for some of them (including Grigorchuk’s group and Thompson’s groups) the compressed word problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete.