Permutations of bounded degree generate groups of polynomial diameter (Q1060843): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q5534298 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The minimum-length generator sequence problem is NP-hard / rank | |||
Normal rank | |||
Latest revision as of 18:23, 14 June 2024
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
