Knuth–Bendix algorithm (General Groups (uncompleted?) Coset Enumeration)

From Algorithm Wiki
Revision as of 11:15, 15 February 2023 by Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.5}^n n^{2} logn)$ == Space Complexity == $O(ng)$??? words (Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1970 == Reference == https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Time Complexity

$O({1.5}^n n^{2} logn)$

Space Complexity

$O(ng)$??? words

(Can store a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g)))

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM?

Year

1970

Reference

https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Knuth–Bendix_algorithm_(General_Groups_(uncompleted%3F)_Coset_Enumeration)&oldid=45358"