Groups -- Complexity -- Cryptology 01 (2009), No. 2, 261--273
Copyright Heldermann Verlag 2009
Space Complexity and Word Problems of Groups
Stephen R. Lakin
Division of Mathematics and Statistics, Faculty of Advanced Technology, University of Glamorgan, Pontypridd CF37 1DL, Great Britain
srlakin@glam.ac.uk
Richard M. Thomas
Dept. of Computer Science, University of Leicester, Leicester LE1 7RH, Great Britain
rmt@mcs.le.ac.uk
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.
[ Fulltext-pdf (139 KB)] for subscribers only.