Obstruction theory and the complexity of counting group homomorphisms

Fix a finite group $G$. We study the computational complexity of counting problems of the following flavor: given a group $\mathrm{\Gamma }$, count the number of homomorphisms $\mathrm{\Gamma }\to G$. Our first result establishes that this problem is $\mathrm{\#}\mathsf{P}$-hard whenever $G$ is a non-abelian group and $\mathrm{\Gamma }$ is provided via a finite presentation. We give several improvements showing that this hardness conclusion continues to hold for restricted $\mathrm{\Gamma }$ satisfying various promises. Our second result shows that if $G$ is class 2 nilpotent and $\mathrm{\Gamma }={\pi }_1(M^3)$ for some input 3-manifold triangulation $M^3$ with $\mathrm{\mid }{H}^2(M,Z(G)\mathrm{\mid }$ bounded above, then there is a polynomial time algorithm to compute the number of homomorphisms from $\mathrm{\Gamma }$ to $G$. This algorithm is explained in part by the fact that 3-manifolds are close enough to being Eilenberg-MacLane spaces for us to solve the necessary group cohomological obstruction problems efficiently using the given triangulation. A similar polynomial time algorithm for counting maps to finite, class 2 nilpotent $G$ exists when $\mathrm{\Gamma }$ is itself a finite group encoded via a multiplication table, provided that $\mathrm{\mid }{H}^2(\mathrm{\Gamma },Z(G))\mathrm{\mid }$ is similarly bounded from above.