Coset Enumeration (Coset Enumeration)

Description

Coset enumeration programs implement systematic procedures for enumerating the cosets of a subgroup H of finite index in a group G, given a set of defining relations for G and words generating H.

Parameters

$n$: number of generators

$g$: order of group (possibly exponential in $n$)

$k$: number of relations

$c$: maximum number of generators multiplied together in a relation

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Todd–Coxeter algorithm	1936	$O({2}^n)$	$O(gkc)$	Exact	Deterministic	Time
Haselgrove-Leech-Trotter (HLT) algorithm	1940	$O({2}^n)$	$O(ng)$?	Exact	Deterministic
Knuth–Bendix algorithm	1970	$O({1.5}^n n^{2} logn)$	$O(ng)$???	Exact	Deterministic	Time

Time Complexity Graph