摘要：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.
关键词：NC^1-hardness; word problem; G-programs; straight-line programs; non-solvable groups; self-similar groups; Thompsonâs groups; Grigorchukâs group
