While reading the post, *Probability of generating a desired permutation by random swaps*, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from its differences sequence?, I got interested in this problem of sorting:

**Input**: a sequence $A$ of $2N$ positive integers (may contain repeated integers).

**Question**: Is it possible to sort sequence $A$ using $N$ transpositions?

Each transposition swaps two non-adjacent elements $a_i$ and $a_j$ in $A$ (two elements are not adjacent if $|i−j|>1$). This means that the two elements can not be adjacent in $A$. I guess the problem should be $NP$-complete.

Is this problem $NP$-complete? Is there an obvious Karp reduction from the $NP$-hard problem in Aaronson's post?

This was posted on TCS SE and had a bounty but without an answer.

P.S. This problem has a nice geometric interpretation: It is equivalent to deciding the existence of a path of length at most N between two points on a special 2N-Permutahedron.

Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one non-adjacent transposition.

non-adjacent entries. Usually we consider either all transpositions, or adjacent transpositions. Paths on the permutohedron definitely correspond to sequences of adjacent transpositions. Also, there is a very simple polynomial time algorithm to decide if you can get from one permutation to another using a given number of adjacent transpositions (because of the definition of "length" of an element of the symmetric group in terms of inversions) $\endgroup$ – Sam Hopkins Apr 2 '18 at 23:45