Proof of Theorem 19 — 3-SAT reduces in polynomial time to MIN-SBPR and to sorting in flips
ProvedPancakeHard.ksat3_reducesThe language -SAT of codes of satisfiable CNF formulas with at most three literals per clause many-one reduces in polynomial time to each of the two languages of Theorem 19:
In the paper: "By reduction from 3-SAT. Given any formula , create (see Definition 8, the construction requires a linear time). By Theorem 18, the minimum number of flips necessary to sort is iff is satisfiable."
Together with the NP-completeness of 3-SAT this gives Theorem 19.
Formalization Note is the published CookLevin.PolyReducible: a total function on binary strings, computed by a multi-tape Turing machine in polynomially many steps, mapping members to members and non-members to non-members. The source language is the published KSat.KSAT 3 (clause width at most ); the reduction must handle every string, including non-codes, formulas with an empty clause, and short clauses.
Differences from the source:
- generalization: reduction from 3-SAT, formulas with exactly three literals per clause (p.20) → reduction from KSat.KSAT 3, clauses of at most three literals; reason: exact-3 formulas are among its instances, so the reduction applies to the paper's 3-SAT; KSAT 3 is the published NP-complete 3-SAT
- reading: the construction requires a linear time → a polynomial-time reduction (CookLevin.PolyReducible); reason: the paper names no machine model; on the published Turing-machine model with the unary list code the output is quadratic in the input for one clause over x_l, so the linear claim is model-dependent, and NP-hardness needs polynomial time
- reading: MIN-SBPR, an optimization problem (sort with a minimum number of flips) → its threshold language sbprLanguage: codes of (k, S) with S a permutation sortable within k flips; reason: NP-hardness of an optimization problem is that of its decision version; an algorithm for the minimum decides the threshold language
- reading: an input sequence (no encoding fixed) → the published unary code CookLevin.encodeListNat of the list; non-codes and non-permutations are rejected; reason: the paper fixes no encoding; the unary code of a permutation is polynomial in its binary size, so hardness transfers
- encoding: sorted in d_b(S) flips → sorted within (at most) d_b(S) flips; reason: no stack sorts in fewer (Property 1), so the two agree
import Mathlib import Definitions.Def_PancakeHard_Languages import Definitions.Def_KSat_Languages set_option autoImplicit false
namespace PancakeHard
/-- The reduction of the proof of **Theorem 19** (Bulteau, Fertin, Rusu, *Pancake Flipping Is Hard*, arXiv:1111.0434v2, §3.3.3, p.26): "By reduction from 3-SAT.
Given any formula φ, create S_φ (see Definition 8, the construction requires a linear time). By
Theorem 18, the minimum number of flips necessary to sort S_φ is d_b(S_φ) iff φ is satisfiable."
3-SAT reduces in polynomial time to MIN-SBPR (threshold form) and to the language of stacks sortable in
`d_b(S)` flips.
**Formalization Note** `KSat.KSAT 3` is the published language of codes `encodeFormula φ` of satisfiable CNF formulas with at most three literals per clause; `≤p` is `CookLevin.PolyReducible`, a many-one reduction computed by a multi-tape Turing machine within a polynomial number of steps. The paper reduces from formulas with exactly three literals per clause; the
reduction stated here starts from the published width-at-most-3 language, which is NP-complete
(`KSat.ksat_npComplete`). The paper's "linear time" names no machine model and is not stated; the
reduction is polynomial-time. -/
theorem ksat3_reduces :
CookLevin.PolyReducible (KSat.KSAT 3) sbprLanguage ∧
CookLevin.PolyReducible (KSat.KSAT 3) tightLanguage := by sorry
end PancakeHard
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.