Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems

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 NC1-hard word problem and...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on computation theory 2023-02, Vol.14 (3-4), p.1-41, Article 11
Main Authors: Bartholdi, Laurent, Figelius, Michael, Lohrey, Markus, Weiß, Armin
Format: Article
Language:English
Subjects:
Algebraic complexity theory
Circuit complexity
Combinatorics
Mathematics of computing
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 NC1-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.
ISSN:1942-3454
1942-3462
DOI:10.1145/3569708