In the general case, I want to say that determining $|Hom(G,H)|$ is incomputable, arguing that you could use the number to test for simplicity of a presentation, but I am new to this area and I keep finding flaws with my argument.


While I believe the general case is incomputable, there are computable special cases. One in particular that interests me is: compute $|Hom(\pi(S),G)|$ for the fundamental group of a surface $S$, given by a triangulation, and $G$ finite. This arises in Mednykh’s Formula for a 2D TLFT invariant ( $|G|^{\chi(S)-1}|Hom(\pi(S),G)|$), which one can approximate (details in a paper to appear by Gorjan Alagic and myself) efficiently on a quantum computer. However, I have been unable to find any information on the classical complexity of finding $|Hom(\pi(S),G)|$ (with $\pi(S),G$ given in any way) to contrast with the quantum case, or even a discussion of when $|Hom(G,H)|$ is computable and what the complexity of computing it should be.


So, that leaves me with the possibly too broad:



> 
> When is $|Hom(G,H)|$ computable for finitely presented $G,H$ and in these special cases what is the classical complexity of computing it?
> 
> 
> 





Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.
Take $G=\mathbb{Z}$. Then computing $|\operatorname{Hom}(G, H)|=|H|$ is the same as computing the size of a finitely presented group, and is thus wildly undecidable. This eliminates both the general case you seem to ask about, and the case of fundamental groups of surfaces (replacing $\mathbb{Z}$ with, say $\mathbb{Z}\oplus \mathbb{Z}$ and letting your surface $S$ be a torus).


In other words, this problem seems essentially intractable as you've asked it. On the other hand, if you restrict $H$ to lie in the class of finite groups, then the complexity is bounded above by $$|H|^{|\text{\# of generators of } G|}\cdot \sum\_r t\_H(|r|)$$
where the sum is taken over the relations of the given presentation of $G$, and where $t\_H(|r|)$ is the time complexity of deciding the word problem in $H$ for a word of length $|r|$. To see this, consider the algorithm which considers all maps $$\{\text{generators of $G$}\to H\}$$
of which there are $$|H|^{|\text{\# of generators of } G|},$$ and for each map, checks whether the relations of $G$ are satisfied in $H$. This algorithm has the time complexity described.


So essentially your question is identical to finding the time complexity of solving the word problem in whatever class of groups $H$ belongs to, about which there is tons of literature.


