Lemma 13 —
ProvedPancakeHard.lemma_13np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a formula over variables with clauses of exactly three literals. Then
Every efficient path from begins by assigning all variables, and every assignment can be reached by efficient flips.
Formalization Note The formula is a list of triples of literals over , and lab is any labelling of its literal occurrences by , with any order of listing the sets , ; the statement quantifies over it.
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: an r-assignment, a partition (T, F) of ⟦1 ; r⟧ → Finsets T, F with r ≤ l, Disjoint T F and T ∪ F = Icc 1 r; r is an explicit argument of S_φ[𝒫]; reason: same instances; a part of a partition may be empty here as in the paper's 0-assignment (∅, ∅)
- 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; reason: for every other φ, S_φ is not the identity and the statement is the paper's
Preamble
import Mathlib import Definitions.Def_PancakeHard_Assignment set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Lemma 13** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.1, p.22): "S_φ ⟹ {S_φ[𝒫] | 𝒫 full assignment}."
**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ᵢ`. -/
theorem lemma_13 (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
(hlab : IsLabelling φ lab) :
LeadsTo (sPhi l φ lab) {S | ∃ T F : Finset ℕ, IsAssignment l l T F ∧ S = sPhiAssign l φ lab l T F} := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.1, p.22, Lemma 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.