Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T15:00:17Z http://mathoverflow.net/feeds/question/64210 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64210/computability-and-complexity-of-computing-homg-h-for-finitely-presented-gro Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H. Edgar A. Bering IV 2011-05-07T16:32:48Z 2011-05-09T11:39:19Z <p>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.</p> <p>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.</p> <p><p>So, that leaves me with the possibly too broad:</p> <blockquote> <p>When is $|Hom(G,H)|$ computable for finitely presented $G,H$ and in these special cases what is the classical complexity of computing it?</p> </blockquote> http://mathoverflow.net/questions/64210/computability-and-complexity-of-computing-homg-h-for-finitely-presented-gro/64215#64215 Answer by Daniel Litt for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H. Daniel Litt 2011-05-07T17:31:04Z 2011-05-07T18:50:19Z <p>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).</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/64210/computability-and-complexity-of-computing-homg-h-for-finitely-presented-gro/64220#64220 Answer by Eric Rowell for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H. Eric Rowell 2011-05-07T17:44:47Z 2011-05-07T17:44:47Z <p>I asked a similar <a href="http://mathoverflow.net/questions/26599/complexity-of-counting-homomorphisms" rel="nofollow">question</a> a while back. In case H is solvable there is an algorithm (see <a href="http://arxiv.org/abs/math/0405122" rel="nofollow">http://arxiv.org/abs/math/0405122</a>) 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 <a href="http://www-fourier.ujf-grenoble.fr/~eiserm/Publications/twistseq.pdf" rel="nofollow">http://www-fourier.ujf-grenoble.fr/~eiserm/Publications/twistseq.pdf</a>). Agol has pointed out that is should be polynomial if H is dihedral in his answer to my question linked above.</p> http://mathoverflow.net/questions/64210/computability-and-complexity-of-computing-homg-h-for-finitely-presented-gro/64377#64377 Answer by HW for Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H. HW 2011-05-09T11:39:19Z 2011-05-09T11:39:19Z <p>This answer is really just intended to add some keywords to the discussion.</p> <p>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</p> <p>$r_1(x_1,\ldots,x_m)=1$</p> <p>$\ldots$</p> <p>$r_n(x_1,\ldots,x_m)=1$</p> <p>in $H$.</p> <p>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 <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=makanin&amp;s5=free&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=15&amp;mx-pid=755956" rel="nofollow">Makanin's Algorithm</a>.</p>