Coset Enumeration: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Problem Description== == Bounds Chart == 350px == Step Chart == 350px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/Factorial | | |- | rowspan="1" | Polynomial > 3 | | |- | rowspan="1" | Cubic | | |- | rows...") |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== | {{DISPLAYTITLE: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 == | |||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | |||
|- | |- | ||
| | |||
| | | [[Todd–Coxeter algorithm (Coset Enumeration Coset Enumeration)|Todd–Coxeter algorithm]] || 1936 || $O({2}^n)$ || $O(gkc)$ || Exact || Deterministic || [https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/0306574AD958F694A0A8339338348AA1 Time] | ||
| | |||
|- | |- | ||
| | | [[Haselgrove-Leech-Trotter (HLT) algorithm (Coset Enumeration Coset Enumeration)|Haselgrove-Leech-Trotter (HLT) algorithm]] || 1940 || $O({2}^n)$ || $O(ng)$? || Exact || Deterministic || | ||
| | |||
| | |||
|- | |- | ||
| | | [[Knuth–Bendix algorithm (Coset Enumeration Coset Enumeration)|Knuth–Bendix algorithm]] || 1970 || $O({1.5}^n n^{2} logn)$ || $O(ng)$??? || Exact || Deterministic || [https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf Time] | ||
| | |||
| | |||
|- | |- | ||
| | |} | ||
== Time Complexity Graph == | |||
[[File:Coset Enumeration - Time.png|1000px]] | |||
Latest revision as of 09:08, 28 April 2023
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
