# Sorting by Strip Swaps is NP-Hard

arXiv: https://arxiv.org/abs/2511.00015 · HTML: https://mlsanity.com/paper/2511.00015/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 13 references that are in the map.
- First posted on arXiv 20 Oct 2025.

## Abstract (arXiv)

We show that Sorting by Strip Swaps (SbSS) is NP-hard by a polynomial reduction of Block Sorting. The key idea is a local gadget, a cage, that replaces every decreasing adjacency (ai,ai+1) by a guarded triple ai,mi,ai+1 enclosed by guards Li,Ui, so the only decreasing adjacencies are the two inside the cage. Small 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.