Definition 8 and §3 — is a permutation of with breakpoints
ProvedPancakeHard.sPhi_stack_size_breakpointsnp-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a boolean formula over variables in conjunctive normal form with clauses of exactly three literals, and let be the sequence of Definition 8 (for any enumeration of the literal occurrences). Then is a permutation of with
The size bound makes the reduction polynomial, and the breakpoint count is the budget of the decision problem of Theorem 19.
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
Preamble
import Mathlib import Definitions.Def_PancakeHard_SPhi set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- Definition 8 and §3 (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, p.20 and p.4): "We define the sequence S_φ as the permutation of ⟦1 ; n⟧
obtained by: …", with `n = 31l + 62k + 12m = 31l + 98k` (p.20), and "the overall reduction for a
formula containing l variables and k clauses creates a stack of 31l + 98k elements with 16l + 50k
breakpoints" (p.4).
**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 sPhi_stack_size_breakpoints (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
(hlab : IsLabelling φ lab) :
IsStack (sPhi l φ lab) ∧ (sPhi l φ lab).length = 31 * l + 98 * φ.length ∧
breakpoints (sPhi l φ lab) = 16 * l + 50 * φ.length := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3, p.4 ("creates a stack of 31l + 98k elements with 16l + 50k breakpoints") and Definition 8, p.20
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.