Timeline for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2011 at 10:41 | comment | added | Derek Holt | 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. | |
| May 8, 2011 at 5:59 | comment | added | Daniel Litt | 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$. | |
| May 8, 2011 at 2:23 | comment | added | Edgar A. Bering IV | 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. | |
| May 7, 2011 at 19:18 | vote | accept | Edgar A. Bering IV | ||
| May 7, 2011 at 18:50 | history | edited | Daniel Litt | CC BY-SA 3.0 |
deleted 6 characters in body
|
| May 7, 2011 at 18:28 | vote | accept | Edgar A. Bering IV | ||
| May 7, 2011 at 18:28 | |||||
| May 7, 2011 at 17:31 | history | answered | Daniel Litt | CC BY-SA 3.0 |