Finding the identity with permutation chains 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!
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.