Semantic correctness of the normalized pancake reductions
ProvedPancakeHard.ReductionProof.semantic_reductionsnp-hardnesspancake-flippingwordram
Let map a canonical, nonempty-clause CNF code of width at most three to the unary list code of the stack of Definition 8, after shifting variable indices and padding short clauses. Let additionally prepend the breakpoint threshold. Both maps return the empty string on other inputs. If these two total maps are computable in polynomial time on the published Turing-machine model, then
This is the semantic part of the proof of Theorem 19, stated with the computability of the fixed maps as an explicit hypothesis. It covers malformed strings, empty clauses, repeated literals, empty formulas, and variable index zero.
Preamble
import Mathlib import Definitions.Def_PancakeHard_ReductionProgram set_option autoImplicit false
Formal statement
namespace PancakeHard.ReductionProof
theorem semantic_reductions (hc : ∀ b : Bool, CookLevin.IsPolyTimeComputable (PancakeHard.ReductionProof.stackCode b)) :
CookLevin.PolyReducible (KSat.KSAT 3) PancakeHard.sbprLanguage ∧
CookLevin.PolyReducible (KSat.KSAT 3) PancakeHard.tightLanguage := by sorry
end PancakeHard.ReductionProof
Source
Bulteau, Fertin, Rusu, Pancake Flipping Is Hard, arXiv:1111.0434v2, Definition 8 and proof of Theorem 19, pp.20,26. Verification lemma for the explicit implementation in PancakeHard_ReductionProgram; parser prefix adapted from accepted submission f1c5da60-9295-4611-bce8-d4b000d4b7f6.