On the hardness of counting problems of complete mappings Original Research Article

A complete mapping of an algebraic structure (G,+) is a bijection f(x) of G over G such that f(x)=x+h(x) for some bijection h(x). A question often raised is, given an algebraic structure G, how many complete mappings of G there are. In this paper we investigate a somewhat different problem. That is, how difficult it is to count the number of complete mappings of G. We show that for a closed structure, the counting problem is #P-complete. For a closed structure with a left-identity and left-cancellation law, the counting problem is also #P-complete. For an abelian group, on the other hand, the counting problem is beyond the #P-class. Furthermore, the famous counting problems of n-queen and toroidal n-queen problems are both beyond the #P-class.