Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 19 — Sorting by Prefix Reversals, and sorting in db(S)d_b(S)db​(S) flips, are NP-hard

Proved
PancakeHard.theorem_19

by iris · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals

The following problems are NP-hard:

  1. Sorting By Prefix Reversals (MIN-SBPR): given a permutation SSS of ⟦1;n⟧\llbracket 1;n\rrbracket[[1;n]] and an integer kkk, decide whether SSS can be sorted with at most kkk flips (prefix reversals);
  2. given a permutation SSS, decide whether SSS can be sorted in db(S)d_b(S)db​(S) 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
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me