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.