Finding the identity with permutation chains

Question

I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.

How hard is to find a sequence $s(j)$ of $U$ subscripts in $[1..K]$, such that $P_{s1}(P_{s2}(...(P_{sU}(Q(i))))) = i$ for every $1\leq i \leq n$, where Q is an initial random permutation.

In other words, the composition of a subset of the given permutations must be the inverse of $Q$.

I suppose this problem, as $n$ grows, is exponential.

Note: the result must be the list of $s(j)$ values, and that list should be polynomial to $n$ in size. I cannot accept something like "apply P1 2^456 times" as an answer.

It is related to any $\sf{NP}$-Complete problem?

Any idea? Thanks!

Answer 1

Yes, this can be solved in polynomial time. Here is an algorithm.

To rephrase the problem statement:

• We are given a basis $P_1,\dots,P_k \in \text{Sym}(n)$ of $k$ random permutations on $\{1,2,\dots,n\}$. We are also given a random permutation $Q \in \text{Sym}(n)$, the target, and we want to find a product of a sequence of $P$'s that yields $Q$. We want the total running time and the length of the sequence to be polynomial.

The algorithm:

• Step 1. Expand the basis so $k\ge 100 n^3$. This can be readily done: we take $b$ to be a bit larger than $2 \lg(100 n^3) + \lg(n!)$ and generate $100 n^3$ random length-$b$ sequences of basis elements. Call the product of the $i$th sequence $P'_i$. Note that the $P'_i$'s look more or less like $100 n^3$ independent random permutations. Thus, we can add all the $P'_i$'s to the basis, and any sequence that uses the $P'_i$'s can be re-expressed as a sequence over the $P_i$'s (at the cost of increasing the sequence length by a factor $b$).

  After Step 1, we can assume that $k \ge 100 n^3$.

• Step 2. Generate all transpositions $(i,j) \in \text{Sym}(n)$. We'll treat each such transposition as the target and find a way to express it as a product over the basis elements. There are $C(n,2)$ such transpositions, so we'll repeat the following step $C(n,2)$ times, once for each desired transposition.

  Suppose we are trying to generate the transposition $(1,2)$, i.e., the permutation that swaps 1 and 2 and leaves all other elements unchanged. For simplicity, I'm going to assume $n$ is odd, but this can be generalized to even $n$, too. We're going to look for a basis element that is good. Call a basis element $P$ good if the cycle structure of $P$ is $(1,2), (3,\dots)$. In other words, $P$ has to contain exactly two cycles: the 2-cycle $(1,2)$, and a $n-2$-cycle that visits all of the other elements. Or, to put it another way, $P(1)=2$, $P(2)=1$, and the orbit of 3 is $\{3,4,\dots,n\}$. Note that if $P$ is good, then $P^{n-2}=(1,2)$. Also, a random permutation is good with probability $(n-3)!/n! \approx 1/n^3$, so with high probability there is at least one good basis element. Thus we can readily find a way to generate the transposition $(1,2)$ using a sequence of length $n-2$. By symmetry, we can do the same for any other transposition. Repeating this procedure $n(n-1)/2$ times yields a way to generate all the transpositions.

• Step 3. Express $Q$ as a product of transpositions. It is easy to express any permutation over $\{1,\dots,n\}$ as a product of at most $n$ transpositions: just find its cycle structure, then express each cycle of length $l$ as a product of $l-1$ transpositions. Since in step 2 we figured out how to express each transposition as a product over the basis elements, this gives us a way to express $Q$, too.

The length of the solution is something like $O(n^3 \lg n)$. The running time of the procedure is something like $O(n^5)$. This is all polynomial.

Answer 2

Just a note: if the $K$ permutations can be arbitrary, and if you want to find the shortest possible solution, a quick reduction from the Pancake flipping problem shows that finding the shortest possible sequence is NP-hard.

The reduction: Given an instance of the Pancake flipping (i.e. a permutation of $[1..n]$), add to the list the $K = n$ possible prefix permutations. The application of a $P_i$ corresponds to a pancake flip, and $U$ of them can generate the identity permutation if and only if the pancake of the original problem can be sorted using $U$ flips.

However, this doesn't apply directly to the problem as you stated it. If we don't need the shortest possible solution, it's easy to find a solution of length $O(n)$ to the pancake flipping problem. Since this question asked for any solution (rather than the shortest possible solution), there's no proof that this problem is NP-hard.