On the Acceptance Power of Groups and Semigroups

We investigate the power of polynomial time machines whose acceptance mechanism is defined by a word problem over some finite semigroup, monoid, or group. For the case of non-solvable groups or monoids (semigroups, resp.) containing non-solvable groups it follows from [HLSVW93] that the according complexity class is PSPACE. For solvable monoids it was shown there that the according class is always a subclass of MOD-PH. We obtain the following results for finite groups: Commutative groups with k elements exactly characterize co-MOD k P, solvable groups with k elements characterize a class that contains co-MOD k P and is contained in (co-MOD k ) r P, the class obtained by r-fold iterated application of the co-MOD k -operator to P. Our results for finite monoids are the following: The classes characterized by commutative finite monoids are the eventually periodic counting classes (see Section 2 for definitions). If we restrict our attention to aperiodic commutative finite monoids, we ob..