Lemma 17 — for a compatible full pair
ProvedPancakeHard.lemma_17np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a full assignment and a full selection such that and are compatible. Then, with ,
A satisfying assignment together with a choice of a true literal in every clause gives an efficient sorting path.
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 17** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.24): "Let 𝒫 be a full assignment and σ be a full selection, such that
𝒫 and σ are compatible (provided such a pair exists for φ). Then S_φ[𝒫, σ] ⟹ 𝓘¹ₙ."
**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). -/
theorem lemma_17 (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
(hlab : IsLabelling φ lab) (T F : Finset ℕ)
(hP : IsAssignment l l T F) (σ : Finset ℕ) (hσ : IsSelection φ lab φ.length σ)
(hc : Compatible φ lab T F σ) :
LeadsTo (sPhiSel l φ lab T F φ.length σ) {identity (31 * l + 98 * φ.length)} := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.3, p.24, Lemma 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.