On the orbits of the product of two permutations (Q1331933)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the orbits of the product of two permutations |
scientific article |
Statements
On the orbits of the product of two permutations (English)
0 references
3 May 1995
0 references
Let \(\alpha\) be a permutation on a finite set \(S\) and \(\text{part}(\alpha)\) denote the partition of \(S\) induced by the orbits of \(\alpha\). Let \(\| A \|\) denote the number of parts of the partition \(A\). A PPP problem is as follows. Given three partitions \(A\), \(B\) and \(C\) of a finite set \(S\), are there permutations \(\alpha\) and \(\beta\) such that \(\text{part}(\alpha) = A\), \(\text{part}(\beta) = B\) and \(\text{part}(\beta \alpha) = C\)? A \(\text{PPP}_ 2\) problem is a PPP problem where \(\| C\| = 2\). This paper shows that the class of \(\text{PPP}_ 2\) problems is NP-complete. When \(\| C \| = 1\), a PPP problem can be solved in polynomial time and space. A PPP problem with given \(A\), \(B\) and \(C\) is said to be planar if \(\| A \| + \| B \| + \| C \| = \| S \| + 2\). It is established that a PPP problem can be solved in polynomial time and space if the problem is planar.
0 references
orbits
0 references
product of two permutations
0 references
permutation
0 references
partition
0 references
polynomial time
0 references
0 references