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

DOI10.1145/3569708MaRDI QIDQ7023433zbMATH OpenFDO

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

Publication date 21 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

zbMATH Keywords

word problemself-similar groupsstraight-line programsGrigorchuk's groupThompson's groupsnon-solvable groupsG-programs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Networks and circuits as models of computation; circuit complexity (68Q06)

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 Q7023433)