I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=(1,2,\ldots,n)$ (i.e., the identity permutation), at each time step $t\in [m]$ we swap the $i_t^{th}$ element in $L$ with the $(i_t+1)^{st}$ element, with independent probability $1/2$. Let $p$ be the probability that $\sigma$ is produced as output.
I'd like to know (any of) the following:
- Is deciding whether $p>0$ an $NP$-complete problem?
- Is calculating $p$ exactly $\#P$-complete?
- What can we say about approximating $p$ to within a multiplicative constant? Is there a PTAS for this?
The variant where the swaps don't need to be of adjacent elements is also of interest.
Note that it's not hard to reduce this problem to edge-disjoint paths (or to integer-valued multicommodity flow); what I don't know is a reduction in the other direction.
Update: OK, checking Garey & Johnson, their problem [MS6] ("Permutation Generation") is as follows. Given as input a target permutation $\sigma\in S_n$, together with subsets $S_1,\ldots,S_m\in [n]$, decide whether $\sigma$ is expressible as a product $\tau_1 \cdots \tau_m$, where each $\tau_i$ acts trivially on all indices not in $S_i$. Garey, Johnson, Miller, and Papadimitriou (behind a paywall, unfortunately) prove that this problem is $NP$-hard.
If the swaps don't need to be adjacent, then I believe this implies that deciding whether $p>0$ is also $NP$-hard. The reduction is simply this: for each $S_1,S_2,\ldots$ in order, we'll offer a set of "candidate swaps" that corresponds to a complete sorting network on $S_i$ (i.e., capable of permuting $S_i$ arbitrarily, while acting trivially on everything else). Then $\sigma$ will be expressible as $\tau_1 \cdots \tau_m$, if and only if it's reachable as a product of these swaps.
This still leaves open the "original" version (where the swaps are of adjacent elements only). For the counting version (with arbitrary swaps), it of course strongly suggests that the problem should be $\#P$-complete. In any case, it rules out a PTAS unless $P=NP$.
