Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems
| Autor: | Bartholdi, Laurent, Figelius, Michael, Lohrey, Markus, Weiß, Armin |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
word problem
Mathematics::Group Theory TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES NC^1-hardness straight-line programs Grigorchuk’s group non-solvable groups self-similar groups G-programs Theory of computation → Algebraic complexity theory Mathematics of computing → Combinatorics Thompson’s groups Theory of computation → Circuit complexity |
| DOI: | 10.4230/lipics.ccc.2020.29 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|