Lemma 16 —
ProvedPancakeHard.lemma_16np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a full assignment. Then
After the assignment, every efficient path selects in each clause a literal that is true under the assignment.
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_Selection set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Lemma 16** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.2, p.24): "Let 𝒫 be a full assignment. Then
S_φ[𝒫] ⟹ {S_φ[𝒫, σ] | σ full selection compatible with 𝒫}."
**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_16 (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
(hlab : IsLabelling φ lab) (T F : Finset ℕ)
(hP : IsAssignment l l T F) :
LeadsTo (sPhiAssign l φ lab l T F)
{S | ∃ σ : Finset ℕ, IsSelection φ lab φ.length σ ∧ Compatible φ lab T F σ ∧
S = sPhiSel l φ lab T F φ.length σ} := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.2, p.24, Lemma 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.