show/hide this revision's text 2 deleted 1405 characters in body

There's a more general consideration from the theory of Burnside groups and the restricted Burnside problem. The free Burnside group $B(m,n)$ is a quotient of a free $m$-generator group by the subgroup generated by $n$th powers, and $B_0(m,n)$ is the quotient by the subgroup which is the intersection of all finite-index subgroups. Zelmanov proved that $B_0(m,n)$ is finite, resolving the restricted Burnside problem. So if $G$ has a presentation with $m$ generators $F_m\to G$, and $|H|=n$, then any homomorphism $G\to H$ will factor through a homomorphism $F_m \to B_0(m,n) \to H$.

Now, if we assume that $m$ is fixed, and that we have computed $B_0(m,n)$, then for relators $r_1,\ldots, r_k \in F_m$ in a presentation of $G$, we ought to be able to find equivalent relations in $F_m$ of bounded length, and which map to the same element of $B_0(m,n)$. This should be easily computable in polynomial time (given a multiplication table for $B_0(m,n)$), and therefore we may replace the $r_i$ with finitely many elements in the free group. So we precompute all homomorphisms from $B_0(m,n)$ to $H$ which kill a finite collection of elements in $B_0(m,n)$, giving a polynomial-time algorithm to compute the number of homomorphisms. So this answers your question in the affirmative for groups given by a finite presentation of bounded rank.

show/hide this revision's text 1

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.

There's a more general consideration from the theory of Burnside groups and the restricted Burnside problem. The free Burnside group $B(m,n)$ is a quotient of a free $m$-generator group by the subgroup generated by $n$th powers, and $B_0(m,n)$ is the quotient by the subgroup which is the intersection of all finite-index subgroups. Zelmanov proved that $B_0(m,n)$ is finite, resolving the restricted Burnside problem. So if $G$ has a presentation with $m$ generators $F_m\to G$, and $|H|=n$, then any homomorphism $G\to H$ will factor through a homomorphism $F_m \to B_0(m,n) \to H$.

Now, if we assume that $m$ is fixed, and that we have computed $B_0(m,n)$, then for relators $r_1,\ldots, r_k \in F_m$ in a presentation of $G$, we ought to be able to find equivalent relations in $F_m$ of bounded length, and which map to the same element of $B_0(m,n)$. This should be easily computable in polynomial time (given a multiplication table for $B_0(m,n)$), and therefore we may replace the $r_i$ with finitely many elements in the free group. So we precompute all homomorphisms from $B_0(m,n)$ to $H$ which kill a finite collection of elements in $B_0(m,n)$, giving a polynomial-time algorithm to compute the number of homomorphisms. So this answers your question in the affirmative for groups given by a finite presentation of bounded rank.