Obstruction theory and the complexity of counting group homomorphisms
For complexity theorists, it establishes hardness and tractability boundaries for counting group homomorphisms, with implications for computational topology and algebra.
The paper proves that counting homomorphisms from a finitely presented group to a fixed non-abelian finite group is #P-hard, and provides polynomial-time algorithms for class 2 nilpotent target groups when the source is a 3-manifold fundamental group or a finite group with bounded second cohomology.
Fix a finite group $G$. We study the computational complexity of counting problems of the following flavor: given a group $Γ$, count the number of homomorphisms $Γ\to G$. Our first result establishes that this problem is $\#\mathsf{P}$-hard whenever $G$ is a non-abelian group and $Γ$ is provided via a finite presentation. We give several improvements showing that this hardness conclusion continues to hold for restricted $Γ$ satisfying various promises. Our second result shows that if $G$ is class 2 nilpotent and $Γ= π_1(M^3)$ for some input 3-manifold triangulation $M^3$ with $|H^2(M,Z(G)|$ bounded above, then there is a polynomial time algorithm to compute the number of homomorphisms from $Γ$ 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 $Γ$ is itself a finite group encoded via a multiplication table, provided that $|H^2(Γ,Z(G))|$ is similarly bounded from above.