2026-07-26T23:09:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12581 2024-03-12T11:59:07Z ddc:004 open_access

Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems Bartholdi, Laurent Figelius, Michael Lohrey, Markus Weiß, Armin NC^1-hardness word problem G-programs straight-line programs non-solvable groups self-similar groups Thompson’s groups Grigorchuk’s group 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 ALOGTIME-hard. For some of these groups (including Grigorchuk’s group and Thompson’s groups) we prove that the circuit value problem (which is equivalent to the circuit evaluation problem) is PSPACE-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laurent Bartholdi and Michael Figelius and Markus Lohrey and Armin Weiß 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.29 urn:nbn:de:0030-drops-125814 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.29 eng https://creativecommons.org/licenses/by/3.0/legalcode