Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Definition
PricingWithTips3DM_048e41d1ffe9e0f282747366

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_d2ae7b422d26e98396abef2f
import Mathlib.Tactic
set_option autoImplicit true
set_option backward.isDefEq.respectTransparency.types false

/-!
# Accepting-boundary alignment for empty stacks

This module isolates the repeated empty-stack block of the concrete
accepting source.  It expands the three generated progressions and identifies
them with the canonical height/cell slots of a non-output stack.
-/

noncomputable section

namespace CLRS.Chapter34.Turing.CookLevin

open PolyBuilder

private theorem accepting_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)

/-- Closed explicit frame list for an empty stack in the accepting row. -/
def verifierAcceptingEmptyStackExpectedFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) :
    List AffineEqFinPairFrame :=
  let tm := W.machine.tm
  let H := (verifierHeight W).eval input.length
  let offset := initialControlWidth tm + cfgStackBitOffset tm H k
  let falseWire := (verifierInitialFalseWirePolynomial W).eval input.length
  [verifierAcceptingFrameAtCoordinate W input offset (falseWire + 1)] ++
    (List.ofFn fun index : Fin H =>
      verifierAcceptingFrameAtCoordinate W input
        (offset + 1 + index.val) falseWire) ++
    (List.ofFn fun cell : Fin H =>
      List.ofFn fun symbol : Fin ((reachableAlphabet tm k).card + 1) =>
        verifierAcceptingFrameAtCoordinate W input
          (offset + (H + 1) +
            ((reachableAlphabet tm k).card + 1) * cell.val + symbol.val)
          (if symbol.val = (reachableAlphabet tm k).card then
            falseWire + 1
          else falseWire)).flatten

/-- The dynamic-first source for an empty stack expands to its closed
height/cell frame list. -/
theorem verifierAcceptingEmptyStackCompiledFrames_eq_expected
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (k : W.machine.tm.K) (input : List Γ) :
    verifierAcceptingEmptyStackCompiledFrames W k input =
      verifierAcceptingEmptyStackExpectedFrames W k input := by
  unfold verifierAcceptingEmptyStackCompiledFrames
    verifierAcceptingEmptyStackExpectedFrames
    verifierAcceptingSegmentFrames verifierAcceptingRowSegmentFrames
  dsimp only
  rw [dynamicFirstAffineEqFinFrames_eq_ofFn,
    dynamicFirstAffineEqFinFrames_eq_ofFn,
    dynamicFirstAffineEqFinRowFrames_eq_flatMap_ofFn]
  apply congrArg₂ (· ++ ·)
  · apply congrArg₂ (· ++ ·)
    · simp only [Polynomial.eval_one]
      rw [List.ofFn_succ, List.ofFn_zero]
      congr 1 <;>
        simp [verifierInitialStackOffsetPolynomial_eval,
          verifierAcceptingPrevious,
          verifierAcceptingFrameAtCoordinate] <;> ring <;> simp
    · apply List.ofFn_inj.mpr
      funext index
      simp [verifierInitialStackOffsetPolynomial_eval,
        verifierAcceptingPrevious,
        verifierAcceptingFrameAtCoordinate] <;> ring <;> simp
  · rw [accepting_flatMap_ofFn_apply]
    apply congrArg List.flatten
    apply List.ofFn_inj.mpr
    funext cell
    rw [show initialBlankCellTargetForms W.machine.tm k =
        List.ofFn (fun symbol : Fin
          ((reachableAlphabet W.machine.tm k).card + 1) =>
            initialPoolTargetForm
              (decide (symbol.val =
                (reachableAlphabet 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 k).card
    <;> simp [verifierInitialStackOffsetPolynomial_eval,
      verifierAcceptingPrevious, verifierAcceptingFrameAtCoordinate,
      affineUnaryTripleFormValue, initialPoolTargetForm, hsymbol]
    <;> ring <;> simp

/-- For a non-output stack, the arithmetic accepting slot map is the same
closed empty height/cell frame list. -/
theorem verifierAcceptingEmptyStackExpectedFrames_eq_slotFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (k : W.machine.tm.K) (hk : k ≠ W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingEmptyStackExpectedFrames W k input =
      (transitionEqStackSlots W.machine.tm
        ((verifierHeight W).eval input.length) k).map
          (verifierAcceptingSlotFrame W hmember input) := by
  have hheightCoordinate
      (height : Fin ((verifierHeight W).eval input.length + 1)) :
      (cfgSlotEquivFin W.machine.tm
          ((verifierHeight W).eval input.length)
          (CfgSlot.stackHeight k height)).val =
        initialControlWidth W.machine.tm +
          cfgStackBitOffset W.machine.tm
            ((verifierHeight W).eval input.length) 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 k).card + 1)) :
      (cfgSlotEquivFin W.machine.tm
          ((verifierHeight W).eval input.length)
          (CfgSlot.stackCell k cell symbol)).val =
        initialControlWidth W.machine.tm +
          cfgStackBitOffset W.machine.tm
            ((verifierHeight W).eval input.length) k +
          (((verifierHeight W).eval input.length) + 1) +
          ((reachableAlphabet W.machine.tm k).card + 1) * cell.val +
          symbol.val := by
    rw [cfgSlotEquivFin_stackCell_val]
    unfold initialControlWidth
    ring
  unfold verifierAcceptingEmptyStackExpectedFrames transitionEqStackSlots
  rw [List.map_append, List.map_flatten, List.map_ofFn]
  simp_rw [List.map_ofFn]
  apply congrArg₂ (· ++ ·)
  · rw [List.ofFn_succ]
    apply congrArg₂ List.cons
    · simp only [Function.comp_apply]
      rw [verifierAcceptingSlotFrame_eq_arithmetic, hheightCoordinate]
      simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight, hk,
        verifierAcceptingFrameAtCoordinate] <;> ring <;> try simp
    · apply List.ofFn_inj.mpr
      funext height
      simp only [Function.comp_apply]
      rw [verifierAcceptingSlotFrame_eq_arithmetic, hheightCoordinate]
      simp [verifierAcceptingSlotRightWire, CfgSlot.stackHeight, hk,
        verifierAcceptingFrameAtCoordinate] <;> ring <;> try simp
  · 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]
    by_cases hsymbol :
        symbol.val = (reachableAlphabet W.machine.tm k).card
    <;> simp [verifierAcceptingSlotRightWire, CfgSlot.stackCell, hk,
      hsymbol, verifierAcceptingFrameAtCoordinate]
    <;> ring <;> try simp

/-- Every non-output stack source is exactly its canonical public-slot map. -/
theorem verifierAcceptingEmptyStackCompiledFrames_eq_slotFrames
    {Γ : Type} {L : Language Γ} (W : VerifierWitness L)
    (hmember : verifierAcceptingSymbol W ∈
      reachableAlphabet W.machine.tm W.machine.tm.k₁)
    (k : W.machine.tm.K) (hk : k ≠ W.machine.tm.k₁)
    (input : List Γ) :
    verifierAcceptingEmptyStackCompiledFrames W k input =
      (transitionEqStackSlots W.machine.tm
        ((verifierHeight W).eval input.length) k).map
          (verifierAcceptingSlotFrame W hmember input) := by
  rw [verifierAcceptingEmptyStackCompiledFrames_eq_expected,
    verifierAcceptingEmptyStackExpectedFrames_eq_slotFrames W hmember k hk]

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