# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 2 Preliminaries and Basic Facts
### Complexity of Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations  
Next, we show an NP-Hardness proof for the sorting distance problem considering some rearrangement models. For this purpose, we define the following decision problems:  
* Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations: given a positive integer \(\lambda\), a rearrangement model \(\mathcal{M}\) containing only \(\lambda\)-operations, a \(\lambda\)-permutation \(\pi\), and a non-negative integer \(k\), decide if it is possible to sort \(\pi\) using, at most, \(k\) operations that belong to \(\mathcal{M}\). * Sorting Permutations by Rearrangements: given a rearrangement model \(\mathcal{M}\), a permutation \(\pi\), and a non-negative integer \(k\), decide if it possible to sort \(\pi\) using, at most, \(k\) operations that belong to \(\mathcal{M}\). When \(\lambda=n\), the problems of Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations are NP-Hard (except for signed reversals), since they are equivalent to the sorting problems without restrictions in the size of operations. Next, we show that the problem is NP-Hard for a wide range of \(\lambda\) values. When the rearrangement model is clear from the context, it is omitted from the instance. **Theorem 1**: _The problem of Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations is NP-Hard when \(\lambda=cn^{d}\), for positive constants \(c\) and \(0<d\leq 1\), considering unsigned reversals, transpositions, transpositions and unsigned reversals, and transpositions and signed reversals._  
Proof. : Consider the model containing only unsigned reversals. The problem of Sorting Permutations by Unsigned Reversals is NP-Hard [2]. Now, we show a reduction from this problem to the problem of Sorting \(\lambda\)-Permutations by Unsigned \(\lambda\)-Reversals when \(\lambda=cn^{d}\), for positive constants \(c\) and \(0<d\leq 1\). Given an instance \((\pi,k)\), where \(\pi\) has size \(n\), for Sorting Permutations by Unsigned Reversals, we create an instance \((\lambda,\mathcal{M},\pi^{\prime},k)\), where \(\lambda=n\), \(\mathcal{M}\) is a model with unsigned \(\lambda\)-reversals, and \(\pi^{\prime}=(\pi_{1}\;\pi_{2}\;\ldots\;\pi_{n}\;(n+1)\;\ldots\;n^{\prime})\), such that \(\lambda=n=cn^{d}\), which is a \(\lambda\)-permutation. We note that, since \(c\) and \(d\) are constants, this is a polynomial-time reduction. Now, we show that the instance \((\pi,k)\) is satisfied for Sorting Permutations by Unsigned Reversals iff \(d^{\lambda}_{r}(\pi^{\prime})\leq k\). (\(\Rightarrow\)) Suppose that there exists a sorting sequence \(S\) of reversals for \(\pi\) with \(k\) reversals or less. Note that \(\pi\) has size \(n\), and all reversals in \(S\) are \(\lambda\)-reversals, since \(\lambda=n\). The sequence \(S\) can sort the \(\lambda\)-permutation \(\pi^{\prime}\); therefore, \(d^{\lambda}_{r}(\pi^{\prime})\leq k\). (\(\Leftarrow\)) Suppose that there exists a sorting sequence \(S^{\prime}\) of \(\lambda\)-reversals for \(\pi^{\prime}\) with \(k\) operations or less. We now construct a sorting sequence \(S\) for \(\pi\) with \(k\) or less reversals. If all operations of \(S^{\prime}\) affect only elements between the positions \(1\) and \(n\) of \(\pi^{\prime}\), then \(S=S^{\prime}\) is also a sorting sequence for \(\pi\). Otherwise, there exists operations in \(S^{\prime}\) which affect the elements in the interval \([n+1,n^{\prime}]\). Let \(S^{\prime}=\rho^{\prime}_{1},\rho^{\prime}_{2},\ldots,\rho^{\prime}_{\ell}\), where \(\ell\) is the length of \(S^{\prime}\). We construct \(S=\rho_{1},\rho_{2},\ldots,\rho_{\ell}\), where \(\rho_{i}\) starts at the first element of \(\rho^{\prime}_{i}\), from left to right, which is in \(\pi\), and it ends at the last element of \(\rho^{\prime}_{i}\) which is in \(\pi\). Since \(S\) inverts the elements of \(\pi\) in the same order as they are inverted in \(\pi^{\prime}\) by \(S^{\prime}\), this sequence sorts \(\pi\).