Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

AbstractIn this paper we investigate the computational difficulty of evaluating and approximately evaluating Pólya′s cycle index polynomial. We start by investigating the difficulty of determining a particular coefficient of the cycle index polynomial. In particular, we consider the following problem, in which i is taken to be a fixed positive integer: Given a set of generators for a permutation group G whose degree, n, is a multiple of i, determine the coefficient of xn/ii in the cycle index polynomial of G. We show that this problem is #P-hard for every fixed i >1. Next, we consider the evaluation problem. Let y1, y2, ... stand for an arbitrary fixed sequence of non-negative real numbers. The cycle index evaluation problem that is associated with this sequence is the following: Given a set of generators for a degree n permutation group G, evaluate the cycle index polynomial of G at the point (y1, ..., yn). We show that if there exists an i such that yi ≠ yi1 and yi ≠ 0 then the evaluation problem associated with y1, y2, ..., is #P-hard. We observe that the evaluation problem is solvable in polynomial time if yj = yj1 for every positive integer j and that it is solvable in polynomial time if yj = 0 for every integer j >1. Finally, we consider the approximate evaluation problem. We show that it is NP-hard to approximately solve the evaluation problem if there exists an i such that yi > yi1. Furthermore, we show that it is NP-hard to approximately solve the evaluation problem if y1 = y2 = ··· = y for some positive non-integer y. We derive some corollaries of our results which deal with the computational difficulty of counting equivalence classes of combinatorial structures