The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups

摘要

We study the computational complexity of counting the number of solutions to systems of equations over a fixed finite semigroup. We show that if the semigroup is a group, the problem is tractable if the group is Abelian and #P-complete otherwise. If the semigroup is a monoid (that is not a group) the problem is #P-complete. In the case of semigroups where all elements have divisors we show that the problem is tractable if the semigroup is a direct product of an Abelian group and a rectangular band, and #P-complete otherwise. The class of semigroups where all elements have divisors contains most of the interesting semigroups e.g. regular semigroups. These results are proved by the use of powerful techniques from universal algebra.