Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 19 — 3-SAT reduces in polynomial time to MIN-SBPR and to sorting in db(S)d_b(S)db​(S) flips

Proved
PancakeHard.ksat3_reduces

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

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

The language 333-SAT of codes of satisfiable CNF formulas with at most three literals per clause many-one reduces in polynomial time to each of the two languages of Theorem 19:

3-SAT≤pMIN-SBPRand3-SAT≤p{S∣S can be sorted in db(S) flips}.3\text{-SAT}\le_p\text{MIN-SBPR}\qquad\text{and}\qquad 3\text{-SAT}\le_p\{S\mid S\text{ can be sorted in }d_b(S)\text{ flips}\}.3-SAT≤p​MIN-SBPRand3-SAT≤p​{S∣S can be sorted in db​(S) flips}.

In the paper: "By reduction from 3-SAT. Given any formula ϕ\phiϕ, create SϕS_\phiSϕ​ (see Definition 8, the construction requires a linear time). By Theorem 18, the minimum number of flips necessary to sort SϕS_\phiSϕ​ is db(Sϕ)d_b(S_\phi)db​(Sϕ​) iff ϕ\phiϕ is satisfiable."

Together with the NP-completeness of 3-SAT this gives Theorem 19.

Formalization Note ≤p\le_p≤p​ is the published CookLevin.PolyReducible: a total function on binary strings, computed by a multi-tape Turing machine in polynomially many steps, mapping members to members and non-members to non-members. The source language is the published KSat.KSAT 3 (clause width at most 333); the reduction must handle every string, including non-codes, formulas with an empty clause, and short clauses.

Differences from the source:

  • generalization: reduction from 3-SAT, formulas with exactly three literals per clause (p.20) → reduction from KSat.KSAT 3, clauses of at most three literals; reason: exact-3 formulas are among its instances, so the reduction applies to the paper's 3-SAT; KSAT 3 is the published NP-complete 3-SAT
  • reading: the construction requires a linear time → a polynomial-time reduction (CookLevin.PolyReducible); reason: the paper names no machine model; on the published Turing-machine model with the unary list code the output is quadratic in the input for one clause over x_l, so the linear claim is model-dependent, and NP-hardness needs polynomial time
  • 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: 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_KSat_Languages

set_option autoImplicit false
Formal statement
namespace PancakeHard

/-- The reduction of the proof of **Theorem 19** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.26): "By reduction from 3-SAT.
Given any formula φ, create S_φ (see Definition 8, the construction requires a linear time). By
Theorem 18, the minimum number of flips necessary to sort S_φ is d_b(S_φ) iff φ is satisfiable."
3-SAT reduces in polynomial time to MIN-SBPR (threshold form) and to the language of stacks sortable in
`d_b(S)` flips.

**Formalization Note** `KSat.KSAT 3` is the published language of codes `encodeFormula φ` of satisfiable CNF formulas with at most three literals per clause; `≤p` is `CookLevin.PolyReducible`, a many-one reduction computed by a multi-tape Turing machine within a polynomial number of steps. The paper reduces from formulas with exactly three literals per clause; the
reduction stated here starts from the published width-at-most-3 language, which is NP-complete
(`KSat.ksat_npComplete`). The paper's "linear time" names no machine model and is not stated; the
reduction is polynomial-time. -/
theorem ksat3_reduces :
    CookLevin.PolyReducible (KSat.KSAT 3) sbprLanguage ∧
      CookLevin.PolyReducible (KSat.KSAT 3) tightLanguage := by sorry

end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.3, p.26, proof of 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