Goldberg, Leslie Ann Automating Pólya theory: The computational complexity of the cycle index polynomial. (English) Zbl 0785.20004 Inf. Comput. 105, No. 2, 268-288 (1993). 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. Reviewer: M.Demlová (Praha) Cited in 3 Documents MSC: 20B40 Computational methods (permutation groups) (MSC2010) 68Q25 Analysis of algorithms and problem complexity 05A15 Exact enumeration problems, generating functions 05A10 Factorials, binomial coefficients, combinatorial functions 05C25 Graphs and abstract algebra (groups, rings, fields, etc.) Keywords:group of permutations; Pólya’s cycle index polynomial; number of cycles; evaluation problem; generators; polynomially solvable; NP-hard PDFBibTeX XMLCite \textit{L. A. Goldberg}, Inf. Comput. 105, No. 2, 268--288 (1993; Zbl 0785.20004) Full Text: DOI