Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.

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?

-
 It is probably not helpful to be given $H$ as a finitely presented group. Even if $H$ is known to be finite, to make any computations in $H$ you would first need to run something like Todd-Coxeter coset enumeration, which has unknown complexity. To even start attempting any meaningful complexity analysis, you would do better to assume for example that $H$ is given as a finite group of permutations. Another situation where you could compute $|{\rm Hom}(G,H)|$ would be $H$ abelian, but again you should assume that $H$ is given as a direct product of cyclic groups. – Derek Holt May 7 2011 at 17:01

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.

-
 Thank you for the pointers. In the case where H is finite this is exponential in the number of generators of $G$, so in the particular case I mentioned above, the genus of the surface $S$ (if one uses the standard presentation for $pi(S)$). Is this the best that can be done classically? In the case where H is solvable the Matei algorithm Eric mentions gives another approach using group cohomology but the complexity isn't clear. – Edgar A. Bering IV May 8 2011 at 2:23 I see no reason why this (extremely naive) algorithm should be optimal, nor a reason to believe it isn't; I'm by no means an expert on this stuff. On the other hand the fundamental groups of surfaces are of a particularly simple form, so it's reasonable to guess there might be a better algorithm. But counting in general is quite computationally difficult--I suspect this problem is not even in $\#P$. – Daniel Litt May 8 2011 at 5:59 I don't believe there is any known algorithm that is not exponential in the number of generators of $H$, but there are ways of making it run faster in practice. The most obvious one is that the image in $H$ of the first generator of $G$ can be restricted to a set of conjugacy class representatives in $H$. You can also make use of the structure of the relators of $G$ to prune the search tree. If some of them only involve a subset of the generators (for example some of them might be powers of single generators), then you can make use of that. Implementations are available in GAP and Magma. – Derek Holt May 8 2011 at 10:41

This answer is really just intended to add some keywords to the discussion.

If $G=\langle x_1,\ldots,x_m\mid r_1,\ldots,r_n\rangle$ then the set $\mathrm{Hom}(G,H)$ is naturally in bijection with the set of solutions to the system of equations

$r_1(x_1,\ldots,x_m)=1$

$\ldots$

$r_n(x_1,\ldots,x_m)=1$

in $H$.

For this reason, the study of $\mathrm{Hom}(G,H)$ is sometimes called 'algebraic (or Diophantine) geometry over $H$'. See the masses of recent literature on the Tarski Problem and related matters, with the key works by Sela and Kharlampovich--Miasnikov, for the case in which $H$ is free. In this case, $\mathrm{Hom}(G,H)$ is infinite if and only if it's non-trivial, which one can determine using Makanin's Algorithm.

-

I asked a similar question 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.

-