证明排序中交换片段问题是计算上困难的。
Sorting by Strip Swaps is NP-Hard
- 用笼子和铰链构造局部结构，将块排序转化为片段交换问题。
- 精确的片段交换方案与完美块排序方案一一对应。
- 适合算法复杂性研究者阅读，理解排序问题的计算难度。
我们通过将块排序（Block Sorting）多项式归约到片段交换排序（Sorting by Strip Swaps, SbSS），证明了SbSS是NP难的。核心思想是引入一种局部构造——‘笼子’（cage），将每个递减相邻对 $(a_i,a_{i+1})$ 替换为受保护的三元组 $a_i,m_i,a_{i+1}$，并由左右守卫 $L_i,U_i$ 包围，使得唯一的递减相邻对仅存在于笼子内部。小的‘铰链’（hinge）结构连接共享元素的相邻笼子，确保移除恰好两个相邻对的片段交换操作，与在原排列中移除恰好一个递减相邻对的块移动操作之间存在双射关系。这一构造建立了精确SbSS调度与完美块调度之间的清晰等价性，从而确立了该问题的NP难性。
原文摘要 · Abstract (English)
We show that \emph{Sorting by Strip Swaps} (SbSS) is NP-hard by a polynomial reduction of \emph{Block Sorting}. The key idea is a local gadget, a \emph{cage}, that replaces every decreasing adjacency $(a_i,a_{i+1})$ by a guarded triple $a_i,m_i,a_{i+1}$ enclosed by guards $L_i,U_i$, so the only decreasing adjacencies are the two inside the cage. Small \emph{hinge} gadgets couple adjacent cages that share an element and enforce that a strip swap that removes exactly two adjacencies corresponds bijectively to a block move that removes exactly one decreasing adjacency in the source permutation. This yields a clean equivalence between exact SbSS schedules and perfect block schedules, establishing NP-hardness.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。