Automating Pólya theory: The computational complexity of the cycle index polynomial (Q1261292)

Let \(G\) be a group of permutations on an \(n\) element set, then Pólya's cycle index polynomial of \(G\) is the \(n\)-variable polynomial \[ P_ G(x_ 1,\dots,x_ n)= (1/| G|) \sum_{g\in G} x_ 1^{c_ 1(g)}\cdots x_ n^{c_ n(g)} \] where \(c_ i(g)\) is the number of cycles of \(g\) of length \(i\). The evaluation problem is the following: Given a set of generators for a degree \(n\) group \(G\) and a sequence \(y_ 1,y_ 2,\dots\) of non-negative real numbers, evaluate \(P_ G(y_ 1,\dots,y_ n)\). It is shown that the evaluation problem is \(\#P\)-hard whenever there exists an \(i\) such that \(y_ i\neq y_ 1^ i\) and \(y_ i\neq 0\). To prove this, it is shown that even determining the coefficient of \(x^{n/i}\) is \(\#P\)-hard for every \(i\), \(i>1\), which divides \(n\). If for the sequence \(y_ 1,y_ 2,\dots\) it holds either \(y_ j=y_ 1^ j\) for every \(j>1\), or \(y_ 1=y_ 2=\dots=0\), then the evaluation problem is polynomially solvable. Further, the approximate evaluation problem is considered. It is shown that it is NP-hard to approximately solve the evaluation problem if either there exists an \(i\) such that \(y_ i>y_ 1^ i\) or \(y_ 1=y_ 2=\dots=y\) for some positive non-integer \(y\). The combinatorial significance is presented of the cycle index polynomial and corollaries are derived for the computational difficulty of counting equivalence classes of combinatorial structures.