Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ requiring that decomposition to be somehow "short" (and assuming it exists) ? ("Short" - for example linear or polynomial in diameter of the subgroup generated by $p_i$). Any references/ideas/expectations are welcome.
Question 2: Assume additional constraint - the subgroup generated by $p_i$ is nilpotent finite group. Can one expect that finding "short" decomposition would have polynomial complexity in that case ?
Context:
Schreier-Sims seems NOT to be effective: Carlo Beenakker: MO474712 "The Schreier-Sims algorithm is highly inefficient, as explained here." Igor Pak comment here: "the word lengths can increase exponentially, so if you want to write an explicit word - the Schreier–Sims is useless".
Finding OPTIMAL (i.e. the shortest length) is known to be hard problem, even for some particular choices of generators: "Solving the Rubik's Cube Optimally is NP-complete" (see also: TCS783), "Bill Gates pancake sorting problem": "Pancake Flipping Is Hard". For generic generators and given integer "K" determining can element be decomposed as product of "K" generators is NP-hard: "The minimum-length generator sequence problem is NP-hard"( S. Even, O. Goldreich 1981) and also "complete for PSPACE with respect to log-space reducibility" (M. Jerrum 1985). See also MO139469.
So finding constantly short decompositions - is hard, without shortness constraint it is not, but what is in between seems to be not so clear.
