This is a question I have thought about and asked a number of people, but have never got an answer beyond "It should be true that..."


Given a finitely generated group $G$ (eg. a link group $G\_L:=\pi\_1(S^3-L)$ for a link $L$) and a finite group $H$ we want to count homomorphisms from $G$ to $H$. For link groups as above, this is an invariant of $L$. 


My question: (for which $H$) is there a polynomial-time algorithm (in the number of generators and relations for $G$) for computing $N(G,H):=|Hom(G,H)|$ (particularly for $G\_L$)?


Some things I know: 
1) If $L$ is a knot and $H$ is nilpotent then $N(G\_L,H)$ is constant ([M. Eisermann](https://www.ams.org/journals/proc/2000-128-05/S0002-9939-99-05287-9/home.html))
2) [D. Matei; A. I. Suciu,](http://doi:10.1016/j.jalgebra.2005.01.009) have an algorithm for solvable $H$, but the complexity is not clear.
3) The abelianization of $G\_L$ is just $Z^c$, $c$ the number of components, so for $H$ abelian it is easy.


A wild conjecture is that it should always be "FPRASable" i.e. there exists a fully polynomial randomized approximation scheme for the computation.



complexity of counting homomorphisms
For $G$ a knot group, and for $H$ a dihedral group, there should be a simple algorithm for counting the number of homomorphisms. The meridians of $G$ normally generate, and are all conjugate, so they must be sent to conjugate elements in $H$. If they are sent to the cyclic subgroup of index 2, then the image is cyclic, and this is easy to count. 


If a meridian is sent to an involution, then an index 2 subgroup of $G$ is sent to a cyclic group. This amounts to computing the homology of the 2-fold branched cover of the knot, together with the action of the involution on this homology. This is certainly polynomial-time computable, and I'm pretty sure one can determine its dihedral quotients easily. In any case, at least this reduces it to the problem of finding dihedral quotients of abelian-by-$\mathbb{Z}/2$ groups. 


