Permutations of bounded degree generate groups of polynomial diameter (Q1060843)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Permutations of bounded degree generate groups of polynomial diameter |
scientific article |
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
