# Sorting by Multi-Cut Rearrangements +
## 2 Sorting by Multi-Cut Rearrangements in Strings
: _For any \(p\geq 3\), Balanced \(p\)-Partition is strongly NP-hard._  
Proof. : First, we show that for any \(p\geq 3\), \(p\)-Partition is strongly NP-hard, by reduction from 3-Partition. Indeed, consider an instance \((\mathcal{A},B)\) of 3-Partition, with \(\mathcal{A}=\{a_{1},a_{2},\ldots,a_{3m}\}\) and \(B=\frac{1}{m}\sum_{i=1}^{3m}a_{i}\). Let \(N=B+1\). We now construct an instance \((\mathcal{A}^{\prime},B^{\prime})\) of \(p\)-Partition as follows: for any \(1\leq i\leq 3m\), \(a_{i}^{\prime}=a_{i}\), while \(a_{i}^{\prime}=N\) for all \(3m+1\leq i\leq pm\). Let \(B^{\prime}=\frac{1}{m}\sum_{i=1}^{pm}a_{i}^{\prime}\). Then, \(B^{\prime}=\frac{1}{m}(\sum_{i=1}^{m}a_{i}+(p-3)mN)\), that is \(B^{\prime}=B+(p-3)N\). Note that \(B^{\prime}<(p-2)N\). (\(\Rightarrow\)) If \((\mathcal{A},B)\) is a Yes-instance for 3-Partition, then assume that \(\mathcal{A}\) can be partitioned into \(A_{1},A_{2},\ldots,A_{m}\). Now, for any \(1\leq j\leq m\), take \(A_{j}^{\prime}\) to be the union of \(A_{j}\) and of any \((p-3)\) of the remaining elements among \(a_{3m+1}^{\prime},a_{3m+2}^{\prime},\ldots,a_{pm}^{\prime}\). The sum of the elements \begin{table}
\begin{tabular}{c c c} \hline \hline
**Duo** & **Occurrences in \(S\)** & **Occurrences in \(T\)** \\ \hline \((0,0)\) & \(Bm-3m\) & \(Bm-m\) \\ \hline \((0,1)\) & \(3m\) & \(0\) \\ \hline \((0,2)\) & \(0\) & \(m\) \\ \hline \((1,0)\) & \(3m\) & \(0\) \\ \hline \((1,1)\) & \(0\) & \(3m\) \\ \hline \((1,2)\) & \(1\) & \(1\) \\ \hline \((2,0)\) & \(0\) & \(m\) \\ \hline \((2,1)\) & \(0\) & \(0\) \\ \hline \((2,2)\) & \(m\) & \(0\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Exhaustive list of duos present both in \(S\) and \(T\), together with their occurrences. in \(A^{\prime}_{j}\) is equal to \(B^{\prime}\), and sets \(A^{\prime}_{j}\) together form a partition of \(\mathcal{A}^{\prime}\). Hence, \((\mathcal{A}^{\prime},B^{\prime})\) is a Yes-instance for \(p\)-Partition. (\(\Leftarrow\)) If \((\mathcal{A}^{\prime},B^{\prime})\) is a Yes-instance for \(p\)-Partition, then assume that \(\mathcal{A}^{\prime}\) can be partitioned into \(A^{\prime}_{1},A^{\prime}_{2},\ldots,A^{\prime}_{m}\). Any \(A^{\prime}_{i}\) contains at least three elements among \(\{a^{\prime}_{1},a^{\prime}_{2},\ldots,a^{\prime}_{3m}\}\), otherwise the sum of elements of \(A^{\prime}_{j}\) would be at least \((p-2)N>B^{\prime}\). Since there are \(3m\) such elements, we conclude that each \(A^{\prime}_{j}\) must contain exactly three elements of \(\mathcal{A}\). Now, let \(A_{j}=A^{\prime}_{j}\cap\mathcal{A}\). Let \(S_{j}\) (resp. \(S^{\prime}_{j}\)) be the sum of the elements of \(A_{j}\) (resp. \(A^{\prime}_{j}\)). Then, we have \(S^{\prime}_{j}=S_{j}+(p-3)N\). Since \(S^{\prime}_{j}=B^{\prime}\), we conclude that \(S_{j}=B\). This shows that \(A_{1},A_{2},\ldots,A_{m}\) is a partition of \(\mathcal{A}\) for which each set is of cardinality \(3\) and sums to \(B\). In other words, \((\mathcal{A},B)\) is a Yes-instance for \(3\)-Partition. Finally, the following argument shows that \(p\)-Partition remains strongly NP-hard in the balanced restriction. Indeed, take any instance of \(p\)-Partition and modify it as follows: every \(a^{\prime}_{i}\) is increased by \(B^{\prime}\), and set \(B^{\prime\prime}=(p+1)B^{\prime}\). In that case, the sum of all elements from \(\mathcal{A}^{\prime}\) is \(m(p+1)B^{\prime}\), and if a partition \(A^{\prime}_{1},A^{\prime}_{2},\ldots,A^{\prime}_{m}\) exists, the sum of the elements of each \(A^{\prime}_{j}\) is equal to \(B^{\prime\prime}\). Since \(a^{\prime}_{i}>B^{\prime}\), we conclude that \(a^{\prime}_{i}>\frac{B^{\prime\prime}}{p+1}\) and we are done. Note that each \(a^{\prime}_{i}\) remains bounded by a polynomial on the instance size (since each \(a_{i}\) and \(B\) is polynomialy bounded in \(3\)-Partition), hence preserving the strong NP-hardness. Proof of Theorem 3.: Now, in order to prove that SMCR is NP-hard in ternary strings for any odd \(k\geq 7\), it suffices to adapt the reduction provided in proof of Theorem 2.