Theorem 19 — Sorting by Prefix Reversals, and sorting in flips, are NP-hard
ProvedPancakeHard.theorem_19np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals
The following problems are NP-hard:
- Sorting By Prefix Reversals (MIN-SBPR): given a permutation of and an integer , decide whether can be sorted with at most flips (prefix reversals);
- given a permutation , decide whether can be sorted in flips, the number of its breakpoints.
The breakpoint count is the classical lower bound on the number of flips; the second statement says that already deciding whether this lower bound is tight is NP-hard, which answers the long-open question of the complexity of the pancake problem.
Formalization Note NP-hardness is the published CookLevin.NPHard: every language with a polynomial-time Turing-machine verifier reduces to the language by a polynomial-time many-one reduction. Both languages consist of the unary codes CookLevin.encodeListNat of their instances and reject non-codes and lists that are not permutations.
Differences from the source:
- reading: MIN-SBPR, an optimization problem (sort with a minimum number of flips) → its threshold language sbprLanguage: codes of (k, S) with S a permutation sortable within k flips; reason: NP-hardness of an optimization problem is that of its decision version; an algorithm for the minimum decides the threshold language
- reading: NP-hard (no model of computation named) → CookLevin.NPHard: every InNP language (polynomial-time multi-tape Turing-machine verifier) is ≤p the language; reason: the standard definition, on the platform's published machine model
- reading: an input sequence (no encoding fixed) → the published unary code CookLevin.encodeListNat of the list; non-codes and non-permutations are rejected; reason: the paper fixes no encoding; the unary code of a permutation is polynomial in its binary size, so hardness transfers
- encoding: sorted in d_b(S) flips → sorted within (at most) d_b(S) flips; reason: no stack sorts in fewer (Property 1), so the two agree
Preamble
import Mathlib import Definitions.Def_PancakeHard_Languages import Definitions.Def_CookLevin_Complexity set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Theorem 19** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.26): "The following problems are NP-hard:
• Sorting By Prefix Reversals (MIN-SBPR)
• deciding, given a sequence S, whether S can be sorted in d_b(S) flips"
**Formalization Note** NP-hardness is the published `CookLevin.NPHard`: every language in NP (a
polynomial-time Turing-machine verifier) reduces to the language by a polynomial-time many-one
reduction. MIN-SBPR is its threshold language `sbprLanguage` (pairs `(S, k)`, `S` sortable within `k`
flips); the second problem is `tightLanguage` (stacks `S` sortable within `d_b(S)` flips). Both use the
published unary code `CookLevin.encodeListNat` and reject non-codes and non-permutations. -/
theorem theorem_19 :
CookLevin.NPHard sbprLanguage ∧ CookLevin.NPHard tightLanguage := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.3, p.26, Theorem 19
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.