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
    0 references
    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

    Identifiers