摘要：The Cayley semigroup membership problem asks, given a multiplication table representing a semigroup , a subset of and an element of , whether can be expressed as a product of elements of . It is well-known that this problem is NL-complete under AC0 -reductions. For groups, the problem can be solved in deterministic Logspace. This raised the question of determining the exact complexity of this variant. Barrington, Kadau, Lange and McKenzie showed that for Abelian groups and for certain solvable groups, the problem is contained in the complexity class FOLL (polynomial-size, (log log )-depth circuits) and they concluded that these variants are not hard, under AC0 reductions, for any complexity class containing the Parity language. The more general case of arbitrary groups remained open. In this article, we apply results by Babai and Szemerédi directly to this setting to show that the problem is solvable in qAC0 (quasi-polynomial size circuits of constant depth with unbounded fan-in). We prove a similar result for commutative semigroups. Combined with the Yao–Håstad circuit lower bound, it follows immediately that Cayley semigroup membership for groups and Cayley semigroup membership for commutative semigroups are not hard, under AC0 reductions, for any class containing Parity. Moreover, we prove that NL-completeness already holds for the classes of 0-simple semigroups and nilpotent semigroups. Together with our results on groups and commutative semigroups, we prove the existence of a natural class of finite semigroups that generates a variety of finite semigroups with NL-complete Cayley semigroup membership, while the Cayley semigroup membership problem for the class itself is not NL-hard. We also discuss applications of our technique to FOLL and describe varieties for which the Cayley semigroup membership problem is in AC0.
