I asked a similar [question][1] a while back. In case H is solvable there is an algorithm (see http://arxiv.org/abs/math/0405122) but the complexity is not clear.  If H is nipotent and S is a knot complement then M. Eisermann has shown that the $|Hom(\pi(S),H)|$ is constant (see http://www-fourier.ujf-grenoble.fr/~eiserm/Publications/twistseq.pdf). Agol has pointed out that is should be polynomial if H is dihedral in his answer to my question linked above.


  [1]: https://mathoverflow.net/questions/26599/complexity-of-counting-homomorphisms