# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings
For each triple \((a_{i},a_{j},a_{p})\) of the solution, choose a unique substring \(20X0X0X0\) of \(S\) and perform the following three \(k\)-cut rearrangements: first, cut \(S\) around \(0^{a_{i}}\) and around the first copy of \(X\) in the chosen subsequence, and cut at every position inside \(X\). Observe that the number of cuts is exactly \(k\). Now reverse \(X\) into \(X^{\prime}\) and exchange \(0^{a_{i}}\) and \(X^{\prime}\). Perform a similar \(k\)-cut rearrangement with \(a_{j}\) and the second occurrence of \(X\) and with \(a_{p}\) and the third occurrence of \(X\) in the selected substring. The selected substring is transformed into \(200^{a_{i}}00^{a_{i}}0=20^{B+4}\) and since each string \(0^{a_{i}}\) is replaced by \(X^{\prime}\), the first part of the string is \((1X^{\prime})^{3m}\). Hence, the string obtained by the \(3m\) many \(k\)-cut rearrangements described above is \(T\). \((\Leftarrow)\) There are altogether \(6m+(k-2)3m=3 km\) duos in Group 1 which are in excess in \(S\), and \(3 km\) duos in Group 2 which are in excess in \(T\). Since \(\ell=3m\), each \(k\)-cut rearrangement cuts \(k\) duos in Group 1 (and no duo in Group 2 or 3). In particular, no \(00\) duo may be cut in a feasible solution, so each subsequence \(0^{B+4}\) in \(T\) is obtained by concatenating a number of strips of the form \(0^{a_{i}}\), as well as some number \(\delta\) of \(0\) singletons. Since \(S\) has \(4m\) of these singleton \(0\)s, we have \(0\leq\delta\leq 4m\). By the constraint on the values of \(a_{i}\), each subsequence \(0^{B+4}\) in \(T\) contains four singletons from \(S\) and three substrings \(0^{a_{i}}\) of \(S\) whose lengths sum to \(B\). Thus, the \(m\) substrings \(0^{B+4}\) in \(T\) correspond to a partition of \(\mathcal{A}\) into \(m\) sets of three integers whose values sum up to \(B\). Theorem 1 is improved by the following two theorems, which prove the NP-hardness of SMCR in ternary strings, but limited to odd values of \(k\) with \(k\geq 7\). More precisely, Theorem 2 focuses on the specific case \(k=7\), while Theorem 3 extends the result to any odd \(k\geq 7\). Theorem 2: SMCR is NP-hard for \(k=7\) in ternary strings. Proof. : The proof is, as the proof of Theorem 1, by reduction from the strongly NP-hard 3-Partition problem, in which the input is a set \(\mathcal{A}\) of integers and an integer \(B\), and the question is whether \(\mathcal{A}\) can be partitioned into triplets, such that the sum of the integers in each triplet is equal to \(B\). Given an instance \((\mathcal{A},B)\) of 3-Partition with \(\mathcal{A}=\{a_{1},a_{2},\ldots,a_{3m}\}\) such that (i) \(\frac{B}{4}<a_{i}<\frac{B}{2}\) for any \(1\leq i\leq 3m\) and (ii) \(mB=\sum_{i=1}^{3m}a_{i}\), we build the following instance \((S,T,k,\ell)\) of SMCR:  
\[S=10^{a_{1}}10^{a_{2}}\ldots 10^{a_{3m}}12^{m+1}\]  
\[T=1^{3m+1}(20^{B})^{m}2\]with \(k=7\) and \(\ell=m\). Clearly, \(S\) and \(T\) are built on an alphabet of cardinality 3. Now, let us prove the correctness of our reduction. (\(\Rightarrow\)) Suppose the instance \((\mathcal{A},B)\) of 3-Partition is a Yes-instance. Thus, \(\mathcal{A}\) can be partitioned in sets \(A_{1},A_{2},\ldots,A_{m}\), such that \(A_{j}=\{a_{j_{1}},a_{j_{2}},a_{j_{3}}\}\) and \(a_{j_{1}}+a_{j_{2}}+a_{j_{3}}=B\) for any \(1\leq j\leq m\). We now show how to reach \(T\) from \(S\), using 7-cut rearrangements, in \(\ell=m\) steps: at each step \(1\leq j\leq m\), cut in \(S\) to the right of the 1 preceding \(0^{j_{1}}\) (resp. \(0^{j_{2}}\), \(0^{j_{3}}\)) and to the left of the 1 following \(0^{j_{1}}\) (resp. \(0^{j_{2}}\), \(0^{j_{3}}\)), for a total of 6 cuts; the last cut is to the right of the \(j\)-th occurrence of 2. The 6 first cuts allow one to move blocks \(0^{j_{1}}\), \(0^{j_{2}}\), \(0^{j_{3}}\), which we concatenate so as to obtain \(0^{B}\) (since \(a_{j_{1}}+a_{j_{2}}+a_{j_{3}}=B\) by hypothesis). The 7 th cut allows us to insert block \(0^{B}\) between the \(j\)-th and the \((j+1)\)-th copy of 2.