On the Complexity of Some Problems on Groups Input as Multiplication Tables

摘要

The Cayley group membership problem (CGM) is to input a groupoid (binary algebra) 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 classes of groups. The problem for general groups is in SL (symmetric log space), but any kind of hardness result seems difficult because proving it would require constructing the entire multiplication table of a group. We introduce the complexity class FOLL, or FO(log log n), of problems solvable by uniform 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 parity, but FOLL is not known to be contained even in SL. We show that CGM for cyclic groups is in FOLL∩L and that CGM for abelian groups is in FOLL. We then examine the case of some solvable groups, showing in particular that CGM for nilpotent groups is also provably not hard for any class containing parity. We also consider the problem of testing for various properties of a group input as a table: we prove that cyclicity and nilpotency can each be tested in FOLL∩L. Finally, we examine the implications of our results for the complexity of iterated multiplication, powering, and division of integers in the context of the recent results of Chiu, Davida, and Litow and of Hesse.