Space Complexity and Word Problems of Groups
Stephen R. Lakin, Richard M. Thomas · journal of Groups complexity cryptology · 2009
This paper is concerned with the question of determining which groups have their word problems lying in a given complexity class. Our main results give sufficient conditions for the existence of groups whose word problem is contained in some specified space complexity class but is not contained in some other given space complexity class.