# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings
An illustration of the first step of the above described algorithm for solving SMCR is provided in Figure 3.  
After every step \(1\leq j\leq m\) is achieved, three of the \(0^{i_{i}}\) blocks (each one being surrounded by 1s) are removed, while a \(0^{B}\) block is created between two occurrences of 2. Thus, after step \(m\), we have produced sequence \(1^{3m+1}(20^{B})^{m}2=T\). Since every step uses \(k=7\) cuts and \(T\) is obtained after \(m=\ell\) steps, we conclude that \((S,T,k,\ell)\) is a Yes-instance for SMCR. (\(\Leftarrow\)) Suppose that the instance \((S,T,k,\ell)\) that we have built is a Yes-instance. First, we note that \(S\) contains exactly \(7m\) duos (i.e., length-2 substrings) that are absent from \(T\), while \(T\) contains \(7m\) duos that are absent from \(S\), as shown in the exhaustive list of duos provided in Table 2.  
Figure 3: Example of the proposed reduction starting from the following instance of 3-Partition: \(\mathcal{A}=\{6,4,4,7,4,5,4,7,5,5,4,5\}\) (thus \(m=4\)) and \(B=15\). Each \(a_{i}\) is represented by a rectangle containing \(a_{i}\) squares. Colors in \(\mathcal{A}\) describe a way to partition \(\mathcal{A}\) into triplets, each summing to \(B=15\). \(S\) and \(T\) are built as described in the reduction. Each vertical arrow corresponds to a 7-cut. The first one, which is the first step of the proposed 7-cut rearrangement scenario, going from \(S\) to \(S^{\prime}\), is detailed: each red bullet corresponds to a cut, and blocks of 0 that are rearranged are underlined in green (corresponding to the three “green \(a_{i}\)s” summing to \(B\)). Thus, starting from \(S\), and in order to end in \(T\), there are altogether \(7m\) duos to destroy, and \(7m\) to create. Since \(k=7\) and \(\ell=m\), for each of the \(m\) allowed steps, \(7\) duos need to be destroyed (and never further created), while \(7\) duos need to be created (and never further destroyed). In particular, this implies that we never cut strictly inside a block of the form \(0^{a_{i}}\), otherwise a \((0,0)\) duo would be destroyed (whereas the goal is to create altogether \(2m=(B-1)m-(B-3)m\) of them). Since, in \(T\), blocks containing \(0\)s all are of the form \(0^{B}\), this implies that there is a way to arrange all blocks of the form \(0^{a_{i}}\) from \(S\), by concatenating them (and never cutting them), so that we obtain \(m\) blocks of the form \(0^{B}\). This shows that it is possible to partition \(\mathcal{A}\) into \(m\) sets, each achieving a sum equal to \(B\). However, by hypothesis, each \(a_{i}\) satisfies \(\frac{B}{4}<a_{i}<\frac{B}{2}\). Hence, the only way to partition \(\mathcal{A}\) in the above described manner is to group the \(a_{i}\)s by triplets. Consequently, this shows that \((\mathcal{A},B)\) is a Yes-instance for 3-Partition. Proof of Theorem 2 above can be extended so as to prove NP-hardness of SMCR for _any odd \(k\geq 7\)_ in ternary alphabets. This is the purpose of the following theorem. **Theorem 3**. : _SMCR is NP-hard for any odd \(k\geq 7\) in ternary strings._  
The proof is heavily based on the arguments developed in proof of Theorem 2. The idea here is to reduce from a decision problem that we call \(p\)-Partition (\(p\geq 3\) being an integer), which is an extension of 3-Partition; second, we slightly modify strings \(S\) and \(T\) according to this new problem. First, let us formally introduce \(p\)-Partition, and discuss its NP-hardness. The input of \(p\)-Partition is a set \(\mathcal{A}^{\prime}=\{a_{1}^{\prime},a_{2}^{\prime},\ldots,a_{pm}^{\prime}\}\) and an integer \(B^{\prime}\), such that \(mB^{\prime}=\sum_{i=1}^{mp}a_{i}^{\prime}\), and the question is whether \(\mathcal{A}^{\prime}\) can be partitioned into sets \(A_{1}^{\prime}\), \(A_{2}^{\prime}\), \(\ldots\), \(A_{m}^{\prime}\), each of cardinality \(p\), and such that, for any \(1\leq j\leq m\), \(\sum_{a_{i}^{\prime}\in A_{j}^{\prime}}a_{i}^{\prime}=B^{\prime}\). We call Balanced \(p\)-Partition the restriction where \(a_{i}^{\prime}>\frac{B^{\prime}}{p+1}\) for all \(i\). **Lemma 1**.