Permutations of bounded degree generate groups of polynomial diameter (Q1060843)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Permutations of bounded degree generate groups of polynomial diameter |
scientific article; zbMATH DE number 3909734
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Permutations of bounded degree generate groups of polynomial diameter |
scientific article; zbMATH DE number 3909734 |
Statements
Permutations of bounded degree generate groups of polynomial diameter (English)
0 references
1984
0 references
Given an arbitrary permutation h and a set of permutations generating a permutation group G, does h belong to G? This question can be answered in polynomial time on a deterministic Turing machine, but its parallel complexity is unresolved. We are concerned here with the length of a shortest expression for \(h\in G\) as a product of the permutations generating G.
0 references
permutation group
0 references
