Property 11 — clause gadget completion (a. from , b. from , c. from )
ProvedPancakeHard.property_11np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals
Let for pairwise distinct , with from . Let , be any sequences and , disjoint subsets of . Then
- if : ;
- if : ;
- if : .
Once one literal of a clause has been tested, the clause gadget can be cleared provided the two remaining locks are open.
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 is an integer → p : ℤ with -2 ≤ p, offsets written (p + c).toNat; p_Λ and m are natural numbers; reason: the least entry of Γ¹, Γ², Γ³ is p + 3 and Δ contains p + 1, so the stack hypothesis gives p ≥ 0; -2 ≤ p excludes no instance and each (p + c).toNat is p + c; a Literals gadget with m ≥ 1 contains p_Λ + 1; 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
- encoding: O, I disjoint subsets of ⟦1 ; m⟧ → Finset ℕ with O, I ⊆ Icc 1 m and Disjoint O I; reason: same instances
Preamble
import Mathlib import Definitions.Def_PancakeHard_Clause set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Property 11** (clause gadget; Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.2.3, p.18): "Let Y and Z be any sequences, and O, I be two
disjoint subsets of ⟦1 ; m⟧. We have
a. If b, c ∈ O, then ⟨Γ¹, Y, Δ, Z, Λ^O_I⟩ ⟹ ⟨Y, 𝓘^{p+1}_{p+62}, Z, Λ^{O−{b,c}}_{I∪{b,c}}⟩
b. If a, c ∈ O, then ⟨Γ², Y, Δ, Z, Λ^O_I⟩ ⟹ ⟨Y, 𝓘^{p+1}_{p+62}, Z, Λ^{O−{a,c}}_{I∪{a,c}}⟩
c. If a, b ∈ O, then ⟨Γ³, Y, Δ, Z, Λ^O_I⟩ ⟹ ⟨Y, 𝓘^{p+1}_{p+62}, Z, Λ^{O−{a,b}}_{I∪{a,b}}⟩"
for `(γ, Γ, Δ) = Clause(a, b, c, p)` with `a, b, c ∈ ⟦1 ; m⟧` pairwise distinct (Definition 7, p.16) and
`Λ^O_I` that of `Literals(p_Λ, m)` (p.13).
**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. `p` is an integer, as on the page; `-2 ≤ p` excludes no instance, since below it `Γ¹` has a nonpositive entry, and `Δ` contains
`p + 1`, so the stack hypothesis gives `p ≥ 0`. -/
theorem property_11 (pΛ m : ℕ) (p : ℤ) (hp : -2 ≤ p) (a b c : ℕ) (O I : Finset ℕ) (Y Z : List ℕ)
(ha : a ∈ Finset.Icc 1 m) (hb : b ∈ Finset.Icc 1 m) (hc : c ∈ Finset.Icc 1 m)
(hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (hO : O ⊆ Finset.Icc 1 m)
(hI : I ⊆ Finset.Icc 1 m) (hOI : Disjoint O I) :
(b ∈ O → c ∈ O →
IsStack (clauseΓ1 pΛ b c p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I) →
LeadsTo (clauseΓ1 pΛ b c p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I)
{Y ++ interval (p + 1).toNat (p + 62).toNat ++ Z ++ literals pΛ m (O \ {b, c}) (I ∪ {b, c})}) ∧
(a ∈ O → c ∈ O →
IsStack (clauseΓ2 pΛ a c p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I) →
LeadsTo (clauseΓ2 pΛ a c p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I)
{Y ++ interval (p + 1).toNat (p + 62).toNat ++ Z ++ literals pΛ m (O \ {a, c}) (I ∪ {a, c})}) ∧
(a ∈ O → b ∈ O →
IsStack (clauseΓ3 pΛ a b p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I) →
LeadsTo (clauseΓ3 pΛ a b p ++ Y ++ clauseΔ p ++ Z ++ literals pΛ m O I)
{Y ++ interval (p + 1).toNat (p + 62).toNat ++ Z ++ literals pΛ m (O \ {a, b}) (I ∪ {a, b})}) := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.2.3, p.18, Property 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.