Suppose I am given a presentation of a group with a finite number of generators and a finite number of relations. Is there an algorithm for determining if the group is finite? Also, if there is such algorithm, what is the time complexity of the algorithm:
$\endgroup$1 Answer
$\begingroup$No that problem is known to be undecidable in general. Even the problem of deciding whether the group is trivial is undecidable.
It is semi-decidable in the sense that if the group defined by the presentation is finite, then it is possible to prove that it is finite and to determine its order. The Todd-Coxeter coset enumeration procedure, of which there are good implementations, is probably the best way of doing this in practice. But the fact that the general problem is undecidable implies immediately that you cannot bound the complexity of this process by any recursive function.
$\endgroup$
