On the complexity of some problems on groups input as multiplication tables

The Cayley group membership problem (CGM) is to input a groupoid (binary al gebra) G given as a multiplication table, a subset X of G, and an element t of G and to determine whether t can be expressed as a product of elements of X. For general groupoids CGM is P-complete, and for associative algebras (semigroups) it is NL-complete. Here we investigate CGM for particular cla sses of groups. The problem for general groups is in SL (symmetric log spac e), but any kind of hardness result seems difficult because proving it woul d require constructing the entire multiplication table of a group. We intro duce the complexity class FOLL, or FO(log log n), of problems solvable by u niform poly-size circuit families of unbounded fan-in and depth O(log log n ). No problem in FOLL can be hard for L or for any other class containing p arity, but FOLL is not known to be contained even in SL. We show that CGM f or cyclic groups is in FOLL boolean AND L and that CGM for abelian groups i s in FOLL. We then examine the case of some solvable groups, showing in par ticular that CGM for nilpotent groups is also provably not hard for any cla ss containing parity. We also consider the problem of testing for various p roperties of a group input as a table: we prove that cyclicity and nilpoten cy can each be tested in FOLL boolean AND L. Finally, we examine the implic ations of our results for the complexity of iterated multiplication, poweri ng, and division of integers in the context of the recent results of Chiu, Davida, and Litow and of Hesse. (C) 2001 Academic Press.