Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

PricingWithTips 3DM dependency: CLRSLean.Chapter_34.Section_34_4_NP_Completeness_Proofs.CookLevin.Circuitization.GeneratorAcceptingBoundaryOutputStackAlignment

Definition
PricingWithTips3DM_249e04f8ad34e348cf12f6b6

by qmaai2907271020 · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorypricing-with-tipsthree-dimensional-matching

A private, kernel-checked dependency module used by the formal NP-hardness proof for three-dimensional matching and Theorems 4.1 and 4.2 of arXiv:2507.10872.

Definition code
import Definitions.Def_PricingWithTips3DM_048e41d1ffe9e0f282747366
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Accepting-boundary alignment for the output stack

The distinguished output stack has height one, contains the accepting symbol
in cell zero, and is blank thereafter.  This module expands exactly those five
source segments before aligning them with the canonical stack slots.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem acceptingOutput_flatMap_ofFn_apply
    {α β : Type} {count : Nat} (items : Fin count → α)
    (emit : α → List β) :
    (List.ofFn items).flatMap emit =
      (List.ofFn fun index => emit (items index)).flatten := by
  induction count with
  | zero => rfl
  | succ count ih =>
      rw [List.ofFn_succ, List.ofFn_succ]
      simp only [List.flatMap_cons, List.flatten_cons]
      congr 1
      exact ih (fun index => items index.succ)

private theorem acceptingOutput_ofFn_eq_cons_of_add_one_eq
    {α : Type} {tail H : Nat} (hsize : tail + 1 = H)
    (items : Fin H → α) :
    List.ofFn items =
      items ⟨0, by omega⟩ ::
        List.ofFn (fun index : Fin tail =>
          items ⟨index.val + 1, by omega⟩) := by
  subst H
  rw [List.ofFn_succ]
  congr 1

/-- Closed segmented frame list for the distinguished accepting output
stack. -/
def verifierAcceptingOutputStackExpectedFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) : List AffineEqFinPairFrame :=
  let tm := W.machine.tm
  let k := tm.k₁
  let width := (reachableAlphabet tm k).card + 1
  let tail := (verifierAcceptingHeightTailPolynomial W).eval input.length
  let H := (verifierHeight W).eval input.length
  let offset := initialControlWidth tm + cfgStackBitOffset tm H k
  let cells := offset + H + 1
  let falseWire := (verifierInitialFalseWirePolynomial W).eval input.length
  let outputCode := encodeAlphabetSymbol tm k
    (verifierAcceptingSymbol W) hmember
  [verifierAcceptingFrameAtCoordinate W input offset falseWire] ++
    [verifierAcceptingFrameAtCoordinate W input (offset + 1)
      (falseWire + 1)] ++
    (List.ofFn fun index : Fin tail =>
      verifierAcceptingFrameAtCoordinate W input
        (offset + 2 + index.val) falseWire) ++
    (List.ofFn fun symbol : Fin width =>
      verifierAcceptingFrameAtCoordinate W input
        (cells + symbol.val)
        (if symbol = outputCode then falseWire + 1 else falseWire)) ++
    (List.ofFn fun cell : Fin tail =>
      List.ofFn fun symbol : Fin width =>
        verifierAcceptingFrameAtCoordinate W input
          (cells + width + width * cell.val + symbol.val)
          (if symbol.val = (reachableAlphabet tm k).card then
            falseWire + 1
          else falseWire)).flatten

/-- The five generated output-stack segments expand to the closed accepting
height/output/blank-cell list. -/
theorem verifierAcceptingOutputStackCompiledFrames_eq_expected
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingOutputStackCompiledFrames W hmember input =
      verifierAcceptingOutputStackExpectedFrames W hmember input := by
  unfold verifierAcceptingOutputStackCompiledFrames
    verifierAcceptingOutputStackExpectedFrames
    verifierAcceptingSegmentFrames verifierAcceptingRowSegmentFrames
  dsimp only
  rw [dynamicFirstAffineEqFinFrames_eq_ofFn,
    dynamicFirstAffineEqFinFrames_eq_ofFn,
    dynamicFirstAffineEqFinFrames_eq_ofFn,
    dynamicFirstAffineEqFinRowFrames_eq_flatMap_ofFn,
    dynamicFirstAffineEqFinRowFrames_eq_flatMap_ofFn]
  apply congrArg₂ (· ++ ·)
  · apply congrArg₂ (· ++ ·)
    · apply congrArg₂ (· ++ ·)
      · apply congrArg₂ (· ++ ·)
        · simp only [Polynomial.eval_one]
          rw [List.ofFn_succ, List.ofFn_zero]
          congr 1
          simp [verifierInitialStackOffsetPolynomial_eval,
            verifierAcceptingPrevious,
            verifierAcceptingFrameAtCoordinate]
        · simp only [Polynomial.eval_one]
          rw [List.ofFn_succ, List.ofFn_zero]
          congr 1
          simp [verifierInitialStackOffsetPolynomial_eval,
            verifierAcceptingPrevious,
            verifierAcceptingFrameAtCoordinate] <;> ring
      · apply List.ofFn_inj.mpr
        funext index
        simp [verifierInitialStackOffsetPolynomial_eval,
          verifierAcceptingPrevious,
          verifierAcceptingFrameAtCoordinate] <;> ring <;> simp
    · simp only [Polynomial.eval_one]
      conv_lhs => rw [List.ofFn_succ, List.ofFn_zero]
      simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil]
      rw [show acceptingOutputCellTargetForms W hmember =
          List.ofFn (fun symbol : Fin
            ((reachableAlphabet W.machine.tm W.machine.tm.k₁).card + 1) =>
              initialPoolTargetForm
                (decide (symbol = encodeAlphabetSymbol W.machine.tm
                  W.machine.tm.k₁ (verifierAcceptingSymbol W)
                    hmember))) by rfl]
      rw [affineEqFinRowFrames_ofFn]
      apply List.ofFn_inj.mpr
      funext symbol
      by_cases hsymbol : symbol = encodeAlphabetSymbol W.machine.tm
          W.machine.tm.k₁ (verifierAcceptingSymbol W) hmember
      <;> simp [verifierInitialStackOffsetPolynomial_eval,
        verifierAcceptingPrevious, verifierAcceptingFrameAtCoordinate,
        affineUnaryTripleFormValue, initialPoolTargetForm, hsymbol]
      <;> ring <;> simp
  · rw [acceptingOutput_flatMap_ofFn_apply]
    apply congrArg List.flatten
    apply List.ofFn_inj.mpr
    funext cell
    rw [show initialBlankCellTargetForms W.machine.tm W.machine.tm.k₁ =
        List.ofFn (fun symbol : Fin
          ((reachableAlphabet W.machine.tm W.machine.tm.k₁).card + 1) =>
            initialPoolTargetForm
              (decide (symbol.val =
                (reachableAlphabet W.machine.tm W.machine.tm.k₁).card))) by
          rfl]
    rw [affineEqFinRowFrames_ofFn]
    apply List.ofFn_inj.mpr
    funext symbol
    by_cases hsymbol : symbol.val =
        (reachableAlphabet W.machine.tm W.machine.tm.k₁).card
    <;> simp [verifierInitialStackOffsetPolynomial_eval,
      verifierAcceptingHeightTailPolynomial_eval_add_one,
      verifierAcceptingPrevious, verifierAcceptingFrameAtCoordinate,
      affineUnaryTripleFormValue, initialPoolTargetForm, hsymbol]
    <;> ring <;> simp

/-- The closed output-stack source is precisely the canonical height and
cell slot map for the distinguished stack. -/
theorem verifierAcceptingOutputStackExpectedFrames_eq_slotFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingOutputStackExpectedFrames W hmember input =
      (transitionEqStackSlots W.machine.tm
        ((verifierHeight W).eval input.length) W.machine.tm.k₁).map
          (verifierAcceptingSlotFrame W hmember input) := by
  have htail := verifierAcceptingHeightTailPolynomial_eval_add_one W
    input.length
  have hheightCoordinate
      (height : Fin ((verifierHeight W).eval input.length + 1)) :
      (cfgSlotEquivFin W.machine.tm
          ((verifierHeight W).eval input.length)
          (CfgSlot.stackHeight W.machine.tm.k₁ height)).val =
        initialControlWidth W.machine.tm +
          cfgStackBitOffset W.machine.tm
            ((verifierHeight W).eval input.length) W.machine.tm.k₁ +
          height.val := by
    rw [cfgSlotEquivFin_stackHeight_val]
    unfold initialControlWidth
    ring
  have hcellCoordinate
      (cell : Fin ((verifierHeight W).eval input.length))
      (symbol : Fin
        ((reachableAlphabet W.machine.tm W.machine.tm.k₁).card + 1)) :
      (cfgSlotEquivFin W.machine.tm
          ((verifierHeight W).eval input.length)
          (CfgSlot.stackCell W.machine.tm.k₁ cell symbol)).val =
        initialControlWidth W.machine.tm +
          cfgStackBitOffset W.machine.tm
            ((verifierHeight W).eval input.length) W.machine.tm.k₁ +
          (((verifierHeight W).eval input.length) + 1) +
          ((reachableAlphabet W.machine.tm W.machine.tm.k₁).card + 1) *
            cell.val + symbol.val := by
    rw [cfgSlotEquivFin_stackCell_val]
    unfold initialControlWidth
    ring
  unfold verifierAcceptingOutputStackExpectedFrames transitionEqStackSlots
  dsimp only
  rw [List.map_append, List.map_flatten, List.map_ofFn]
  simp_rw [List.map_ofFn]
  simp only [List.singleton_append, List.nil_append, List.append_assoc]
  conv_rhs => rw [List.ofFn_succ]
  simp only [List.cons_append, List.nil_append]
  apply congrArg₂ List.cons
  · simp only [Function.comp_apply]
    rw [verifierAcceptingSlotFrame_eq_arithmetic, hheightCoordinate]
    simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
      verifierAcceptingFrameAtCoordinate]
  · rw [acceptingOutput_ofFn_eq_cons_of_add_one_eq htail]
    simp only [List.cons_append, List.nil_append]
    apply congrArg₂ List.cons
    · simp only [Function.comp_apply]
      rw [verifierAcceptingSlotFrame_eq_arithmetic, hheightCoordinate]
      simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
        verifierAcceptingFrameAtCoordinate] <;> ring
    · apply congrArg₂ (· ++ ·)
      · apply List.ofFn_inj.mpr
        funext height
        simp only [Function.comp_apply]
        rw [verifierAcceptingSlotFrame_eq_arithmetic, hheightCoordinate]
        have hne : ((⟨height.val + 1, by omega⟩ : Fin
            ((verifierHeight W).eval input.length)).succ : Fin
              ((verifierHeight W).eval input.length + 1)).val ≠ 1 := by
          simp
        simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight,
          verifierAcceptingFrameAtCoordinate, hne]
        ring
      · conv_rhs =>
          rw [acceptingOutput_ofFn_eq_cons_of_add_one_eq htail,
            List.flatten_cons]
        apply congrArg₂ (· ++ ·)
        · simp only [Function.comp_apply, List.map_ofFn]
          apply List.ofFn_inj.mpr
          funext symbol
          simp only [Function.comp_apply]
          rw [verifierAcceptingSlotFrame_eq_arithmetic, hcellCoordinate]
          by_cases hsymbol : symbol = encodeAlphabetSymbol W.machine.tm
              W.machine.tm.k₁ (verifierAcceptingSymbol W) hmember
          · subst symbol
            simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
              verifierAcceptingFrameAtCoordinate]
            ring
          · have hsymbolVal : symbol.val ≠
                (encodeAlphabetSymbol W.machine.tm W.machine.tm.k₁
                  (verifierAcceptingSymbol W) hmember).val := by
              intro heq
              exact hsymbol (Fin.ext heq)
            simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
              verifierAcceptingFrameAtCoordinate, hsymbol, hsymbolVal]
            ring
        · apply congrArg List.flatten
          apply List.ofFn_inj.mpr
          funext cell
          simp only [Function.comp_apply, List.map_ofFn]
          apply List.ofFn_inj.mpr
          funext symbol
          simp only [Function.comp_apply]
          rw [verifierAcceptingSlotFrame_eq_arithmetic, hcellCoordinate]
          have hcell : (⟨cell.val + 1, by omega⟩ : Fin
              ((verifierHeight W).eval input.length)).val ≠ 0 := by simp
          by_cases hsymbol : symbol.val =
              (reachableAlphabet W.machine.tm W.machine.tm.k₁).card
          <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell,
            verifierAcceptingFrameAtCoordinate, hcell, hsymbol]
          <;> ring

/-- The generated distinguished output stack agrees with its canonical
public-slot block. -/
theorem verifierAcceptingOutputStackCompiledFrames_eq_slotFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingOutputStackCompiledFrames W hmember input =
      (transitionEqStackSlots W.machine.tm
        ((verifierHeight W).eval input.length) W.machine.tm.k₁).map
          (verifierAcceptingSlotFrame W hmember input) := by
  rw [verifierAcceptingOutputStackCompiledFrames_eq_expected,
    verifierAcceptingOutputStackExpectedFrames_eq_slotFrames]

end CLRS.Chapter34.Turing.CookLevin
Source
https://github.com/tanktechnology/CLRS-Lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me