Coset Enumeration (Coset Enumeration)

From Algorithm Wiki
Jump to navigation Jump to search


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.


$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

Coset Enumeration - Time.png