On the orbits of the product of two permutations (Q1331933)

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.