Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems.
2020
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
1
Citations
NaN
KQI