Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 18 — Sϕ⟹In1S_\phi\Longrightarrow\mathcal I_n^1Sϕ​⟹In1​ iff ϕ\phiϕ is satisfiable

Proved
PancakeHard.theorem_18

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

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

Let ϕ\phiϕ be a boolean formula over lll variables with kkk clauses of exactly three literals, and n=31l+98kn=31l+98kn=31l+98k. Then

Sϕ⟹In1  ⟺  ϕ is satisfiable.S_\phi\Longrightarrow\mathcal I_n^1\iff\phi\text{ is satisfiable}.Sϕ​⟹In1​⟺ϕ is satisfiable.

Equivalently (Property 2), SϕS_\phiSϕ​ can be sorted in db(Sϕ)d_b(S_\phi)db​(Sϕ​) flips exactly when ϕ\phiϕ is satisfiable; this is the correctness of the reduction from 3-SAT.

Formalization Note The formula is a list of kkk triples of literals over x1,…,xlx_1,\dots,x_lx1​,…,xl​, and lab is any labelling of its m=3km=3km=3k literal occurrences by ⟦1;m⟧\llbracket 1;m\rrbracket[[1;m]], with any order of listing the sets PiP_iPi​, NiN_iNi​; the statement quantifies over it. For l=k=0l=k=0l=k=0, SϕS_\phiSϕ​ is the empty stack and both sides hold.

Differences from the source:

  • encoding: a boolean formula over l variables in CNF with exactly three literals per clause → a list of triples of CookLevin literals whose variable indices lie in ⟦1 ; l⟧ (IsOverVars l φ); reason: same instances; a variable of x₁, …, x_l need not occur
  • encoding: {λ₁, …, λ_m}, the set of literals, with (aᵢ, bᵢ, cᵢ) the indices of clause i → a labelling lab whose first component lab.1 is a permutation of ⟦1 ; m⟧ giving the index of each occurrence in clause order (IsLabelling); every statement quantifies over all labellings; reason: the paper leaves the enumeration open (p.20); same instances
  • encoding: Pᵢ, Nᵢ as sets in Variable(Pᵢ, Nᵢ, 31(i − 1)) → listed in the order of lab.2, a permutation of ⟦1 ; m⟧; every statement quantifies over it; reason: Definition 6 writes P = {p₁, …, p_q} and leaves the enumeration open, Definition 8 does not fix it; the Pᵢ, Nᵢ are disjoint, so every choice of their enumerations is induced by some lab.2
  • encoding: a path is a series of flips, which goes through T → the list of visited sequences, consecutive ones related by an efficient flip; T is visited if it is in the list, endpoints included; reason: a flip sequence and its visited sequences determine each other on permutations; p.4 (Lemma 13) and Property 2 count endpoints
  • generalization: S_φ ⟹ 𝓘¹ₙ (defined for S_φ different from the identity) → LeadsTo for every φ, including l = k = 0 where S_φ is the empty identity and the empty formula is satisfiable; reason: for every other φ, S_φ is not the identity and the statement is the paper's
Preamble
import Mathlib
import Definitions.Def_PancakeHard_SPhi

set_option autoImplicit false
Formal statement
namespace PancakeHard

/-- **Theorem 18** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.25): "S_φ ⟹ 𝓘¹ₙ iff φ is satisfiable."

**Formalization Note** `φ` is a formula over the variables `x₁, …, x_l` (`IsOverVars l φ`; a variable may not occur) with `k = |φ|` clauses of exactly three literals; `lab` is any enumeration `λ₁, …, λ_{3k}` of its literal occurrences (`IsLabelling`, p.20), which determines `(aᵢ, bᵢ, cᵢ)`, with any order of listing the sets `Pᵢ`, `Nᵢ`. `n = 31l + 98k` (p.20). The paper's `⟹` is defined for sequences other
than the identity; `S_φ` is the identity only for `l = k = 0`, where `LeadsTo` holds (the path with no
flip) and the empty formula is satisfiable. -/
theorem theorem_18 (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
    (hlab : IsLabelling φ lab) :
    LeadsTo (sPhi l φ lab) {identity (31 * l + 98 * φ.length)} ↔ φ.Satisfiable := by sorry

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