Theorem 18 — iff is satisfiable
ProvedPancakeHard.theorem_18np-hardnessp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1pancake-flippingpermutationsprefix-reversals
Let be a boolean formula over variables with clauses of exactly three literals, and . Then
Equivalently (Property 2), can be sorted in flips exactly when is satisfiable; this is the correctness of the reduction from 3-SAT.
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. For , is the empty stack and both sides hold.
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: 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 and the empty formula is satisfiable; reason: for every other φ, S_φ is not the identity and the statement is the paper's
Preamble
import Mathlib import Definitions.Def_PancakeHard_SPhi set_option autoImplicit false
Formal statement
namespace PancakeHard
/-- **Theorem 18** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.25): "S_φ ⟹ 𝓘¹ₙ iff φ is satisfiable."
**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). The paper's `⟹` is defined for sequences other
than the identity; `S_φ` is the identity only for `l = k = 0`, where `LeadsTo` holds (the path with no
flip) and the empty formula is satisfiable. -/
theorem theorem_18 (l : ℕ) (φ : Exact3Formula) (hφ : IsOverVars l φ) (lab : Labelling)
(hlab : IsLabelling φ lab) :
LeadsTo (sPhi l φ lab) {identity (31 * l + 98 * φ.length)} ↔ φ.Satisfiable := by sorry
end PancakeHard
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, §3.3.3, p.25, Theorem 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.