Coset Enumeration

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms


Knuth–Bendix algorithm	1970	$O(1.5^n n^2 \log n)$	$O(ng)$
Haselgrove-Leech-Trotter (HLT) algorithm	1940	$O(2^n)$	$O(ng)$
Todd–Coxeter algorithm	1936	$O(2^n)$	$O(gkc)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms