Property 6 — hook gadget (a. take, b. put, c. release)
ProvedPancakeHard.property_6np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals
Let and let , , be any sequences. Then
- ;
- ;
- .
The hook brings the delimited sequence to the head and stores it back.
Formalization Note Sequences are lists of natural numbers with the head first; the statement assumes, as the paper does throughout (p.2, p.13), that the left-hand sequence is a permutation of , where is its length. The context sequences may be empty.
Differences from the source:
- encoding: a sequence ⟨x₁, …, xₙ⟩ with head element x₁ → a list of natural numbers whose first entry is the head; reason: Lean convention; same instances
- reading: X, Y (, Z) are any sequences → the left-hand sequence is a permutation of ⟦1 ; n⟧, n its length (IsStack); X, Y, Z stay arbitrary and may be empty; reason: p.2: input sequences are permutations of ⟦1 ; n⟧; p.13: all sequences considered are permutations
- encoding: p (and q) are integers → natural numbers; reason: every gadget contains p + 1 (a dock p − 1) and a stack has entries ≥ 1, so a negative offset gives no stack; same instances
- 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
Preamble
import Mathlib import Definitions.Def_PancakeHard_Hook set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Property 6** (hook gadget; Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.1.3, p.7): "Let p be an integer, (take, put, G, H) = Hook(p),
and X, Y and Z be any sequences. We have
a. ⟨take, X, G, Y, H, Z⟩ ⟹ ⟨Y, G′, ⋆X, H′, Z⟩
b. ⟨put, X, G′, ⋆Y, H′, Z⟩ ⟹ ⟨Y, G″, X, H″, Z⟩
c. ⟨G″, X, H″, Y⟩ ⟹ ⟨X, ⋆𝓘^{p+1}_{p+12}, Y⟩"
**Formalization Note** "Any sequences" are read with the paper's convention (p.2; p.13: "all sequences considered are permutations"): the left-hand sequence is a stack, a permutation of `⟦1 ; n⟧` with `n` its length; `X`, `Y`, `Z` may be empty. The head is the first list entry. `⋆X` is `X.reverse`; `p` is a natural number. -/
theorem property_6 (p : ℕ) (X Y Z : List ℕ) :
(IsStack (hookTake p :: X ++ hookG p ++ Y ++ hookH p ++ Z) →
LeadsTo (hookTake p :: X ++ hookG p ++ Y ++ hookH p ++ Z)
{Y ++ hookG' p ++ X.reverse ++ hookH' p ++ Z}) ∧
(IsStack (hookPut p :: X ++ hookG' p ++ Y.reverse ++ hookH' p ++ Z) →
LeadsTo (hookPut p :: X ++ hookG' p ++ Y.reverse ++ hookH' p ++ Z)
{Y ++ hookG'' p ++ X ++ hookH'' p ++ Z}) ∧
(IsStack (hookG'' p ++ X ++ hookH'' p ++ Y) →
LeadsTo (hookG'' p ++ X ++ hookH'' p ++ Y)
{X ++ (interval (p + 1) (p + 12)).reverse ++ Y}) := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.1.3, p.7, Property 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.