Editing Todd–Coxeter algorithm (section)

{{Short description|Algorithm for solving the coset enumeration problem}}
In [[group theory]], the '''Todd–Coxeter algorithm''', created by [[J. A. Todd]] and [[H. S. M. Coxeter]] in 1936, is an [[algorithm]] for solving the [[coset enumeration]] problem.  Given a [[presentation of a group]] ''G'' by generators and relations and a [[subgroup]] ''H'' of ''G'', the algorithm enumerates the [[coset]]s of ''H'' on ''G'' and describes the [[Group_action_(mathematics)#Examples|permutation representation]] of ''G'' on the space of the cosets (given by the left multiplication action). If the [[order of a group]] ''G'' is relatively small and the subgroup ''H'' is known to be uncomplicated (for example, a [[cyclic group]]), then the algorithm can be carried out by hand and gives a reasonable description of the group ''G''. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relations.

The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the [[index (group theory)|index]] of ''H'' in ''G'' is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any [[computable function]] of the index of the subgroup and the size of the input data.