The Complexity of Word and Isomorphism Problems for Finite Groups.
Richard J. Lipton, Lawrence Snyder, Yechezkel Zalcstein · Defense Technical Information Center (DTIC) · 1977
The uniform word problem for finite groups presented by their multiplication tables is considered. Upper bounds of 0(k-squared) for arbitrary group and 0(n log-squared n) for arbitrary semigroup and 0(n log n) for abelian groups are shown where n is the length of the presentation. (Author)