{"id":"arxiv/2602.02885","url":"https://arxiv.org/abs/2602.02885","tags":["math.GR","cs.CC","math.GT"],"score":0,"title":"Obstruction theory and the complexity of counting group homomorphisms","domain":"math.GR","source":"arxiv","authors":["Eric Samperton","Armin Weiß"],"reviews":0,"subject":"math.GR","summary":"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)|$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-02","reactions":{}}